<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<meta name="theme-color" content="#222"><meta name="generator" content="Hexo 6.3.0">

  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">



<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.2.1/css/all.min.css" integrity="sha256-Z1K5uhUaJXA7Ll0XrZ/0JhX4lAtZFpT6jkKrEDT0drU=" crossorigin="anonymous">
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/animate.css/3.1.1/animate.min.css" integrity="sha256-PR7ttpcvz8qrF57fur/yAx1qXMFJeJFiA6pSzWi0OIE=" crossorigin="anonymous">

<script class="next-config" data-name="main" type="application/json">{"hostname":"example.com","root":"/","images":"/images","scheme":"Muse","darkmode":false,"version":"8.14.1","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12},"copycode":{"enable":false,"style":null},"bookmark":{"enable":false,"color":"#222","save":"auto"},"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"stickytabs":false,"motion":{"enable":true,"async":false,"transition":{"menu_item":"fadeInDown","post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"/search.xml","localsearch":{"enable":true,"trigger":"auto","top_n_per_article":-1,"unescape":false,"preload":false}}</script><script src="/js/config.js"></script>

    <meta property="og:type" content="website">
<meta property="og:title" content="JsyBlog">
<meta property="og:url" content="http://example.com/page/9/index.html">
<meta property="og:site_name" content="JsyBlog">
<meta property="og:locale" content="zh_CN">
<meta property="article:author" content="SongyangJi">
<meta name="twitter:card" content="summary">


<link rel="canonical" href="http://example.com/page/9/">



<script class="next-config" data-name="page" type="application/json">{"sidebar":"","isHome":true,"isPost":false,"lang":"zh-CN","comments":"","permalink":"","path":"page/9/index.html","title":""}</script>

<script class="next-config" data-name="calendar" type="application/json">""</script>
<title>JsyBlog</title>
  








  <noscript>
    <link rel="stylesheet" href="/css/noscript.css">
  </noscript>
</head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <div class="column">
      <header class="header" itemscope itemtype="http://schema.org/WPHeader"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏" role="button">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <h1 class="site-title">JsyBlog</h1>
      <i class="logo-line"></i>
    </a>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger" aria-label="搜索" role="button">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu"><li class="menu-item menu-item-home"><a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a></li><li class="menu-item menu-item-tags"><a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a></li><li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a></li><li class="menu-item menu-item-archives"><a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a></li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup"><div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off" maxlength="80"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close" role="button">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div class="search-result-container no-result">
  <div class="search-result-icon">
    <i class="fa fa-spinner fa-pulse fa-5x"></i>
  </div>
</div>

    </div>
  </div>

</header>
        
  
  <aside class="sidebar">

    <div class="sidebar-inner sidebar-overview-active">
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <div class="sidebar-panel-container">
        <!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
        </div>
        <!--/noindex-->

        <div class="site-overview-wrap sidebar-panel">
          <div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">SongyangJi</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
        <a href="/archives/">
          <span class="site-state-item-count">251</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
          <a href="/categories/">
        <span class="site-state-item-count">45</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
          <a href="/tags/">
        <span class="site-state-item-count">109</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>

        </div>
      </div>
    </div>

    
  </aside>


    </div>

    <div class="main-inner index posts-expand">

    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="http://example.com/2022/08/13/Redis%E7%9A%84%E7%83%ADkey%E9%97%AE%E9%A2%98/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="SongyangJi">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="JsyBlog">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="undefined | JsyBlog">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2022/08/13/Redis%E7%9A%84%E7%83%ADkey%E9%97%AE%E9%A2%98/" class="post-title-link" itemprop="url">Redis的热key问题</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2022-08-13 23:50:26" itemprop="dateCreated datePublished" datetime="2022-08-13T23:50:26+08:00">2022-08-13</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar-check"></i>
      </span>
      <span class="post-meta-item-text">更新于</span>
      <time title="修改时间：2022-10-17 10:52:52" itemprop="dateModified" datetime="2022-10-17T10:52:52+08:00">2022-10-17</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/Redis/" itemprop="url" rel="index"><span itemprop="name">Redis</span></a>
        </span>
    </span>

  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <blockquote>
<p>上面提到，所谓热key问题就是，突然有几十万的请求去访问redis上的某个特定key。那么，这样会造成流量过于集中，达到物理网卡上限，从而导致这台redis的服务器宕机。那接下来这个key的请求，就会直接怼到你的数据库上，导致你的服务不可用。</p>
</blockquote>
<h2 id="热Key的危害"><a href="#热Key的危害" class="headerlink" title="热Key的危害"></a>热Key的危害</h2><ul>
<li>流量集中，达到服务器处理上限（<code>CPU</code>、网络 <code>IO</code> 等）；</li>
<li>会影响在同一个 <code>Redis</code> 实例上其他 <code>Key</code> 的读写请求操作；</li>
<li>热 <code>Key</code> 请求落到同一个 <code>Redis</code> 实例上，无法通过扩容解决；</li>
<li>大量 <code>Redis</code> 请求失败，查询操作可能打到数据库，拖垮数据库，导致整个服务不可用。</li>
</ul>
<h2 id="如何发现热Key"><a href="#如何发现热Key" class="headerlink" title="如何发现热Key"></a>如何发现热Key</h2><h3 id="凭借业务经验，预估热-Key-出现"><a href="#凭借业务经验，预估热-Key-出现" class="headerlink" title="凭借业务经验，预估热 Key 出现"></a>凭借业务经验，预估热 Key 出现</h3><p>根据业务系统上线的一些活动和功能，我们是可以在某些场景下提前预估热 <code>Key</code> 的出现的，比如业务需要进行一场商品秒杀活动，秒杀商品信息和数量一般都会缓存到 <code>Redis</code> 中，这种场景极有可能出现热 <code>Key</code> 问题的。</p>
<ul>
<li>优点：简单，凭经验发现热 <code>Key</code>，提早发现提早处理；</li>
<li>缺点：没有办法预测所有热 <code>Key</code> 出现，比如某些热点新闻事件，无法提前预测。</li>
</ul>
<h3 id="客户端进行收集"><a href="#客户端进行收集" class="headerlink" title="客户端进行收集"></a>客户端进行收集</h3><p>一般我们在连接 <code>Redis</code> 服务器时都要使用专门的 SDK（比如：<code>Java</code> 的客户端工具 <code>Jedis</code>、<code>Redisson</code>），我们可以对客户端工具进行封装，在发送请求前进行收集采集，同时定时把收集到的数据上报到统一的服务进行聚合计算。</p>
<ul>
<li>优点：方案简单</li>
<li>缺点：<ul>
<li>对客户端代码有一定入侵，或者需要对 <code>SDK</code> 工具进行二次开发；</li>
<li>没法适应多语言架构，每一种语言的 <code>SDK</code> 都需要进行开发，后期开发维护成本较高。</li>
</ul>
</li>
</ul>
<h3 id="在代理层进行收集"><a href="#在代理层进行收集" class="headerlink" title="在代理层进行收集"></a>在代理层进行收集</h3><p>如果所有的 <code>Redis</code> 请求都经过 <code>Proxy</code>（代理）的话，可以考虑改动 <code>Proxy</code> 代码进行收集，思路与客户端基本类似。</p>
<p><img src="https://gitee.com/dongzl/article-images/raw/master/2021/03-Redis-Hot-Key/Redis-Hot-Key-02.png" alt="img"></p>
<ul>
<li>优点：对使用方完全透明，能够解决客户端 <code>SDK</code> 的语言异构和版本升级问题；</li>
<li>缺点：<ul>
<li>开发成本会比客户端高些；</li>
<li>并不是所有的 <code>Redis</code> 集群架构中都有 <code>Proxy</code> 代理（使用这种方式必须要部署 <code>Proxy</code>）。</li>
</ul>
</li>
</ul>
<h3 id="使用-Redis-自带命令"><a href="#使用-Redis-自带命令" class="headerlink" title="使用 Redis 自带命令"></a>使用 Redis 自带命令</h3><ol>
<li><strong>hotkeys 参数</strong></li>
</ol>
<p><code>Redis</code> 在 <code>4.0.3</code> 版本中添加了 <a target="_blank" rel="noopener" href="https://github.com/redis/redis/pull/4392">hotkeys</a> 查找特性，可以直接利用 <code>redis-cli --hotkeys</code> 获取当前 <code>keyspace</code> 的热点 <code>key</code>，实现上是通过 <code>scan + object freq</code> 完成的。</p>
<ul>
<li>优点：无需进行二次开发，能够直接利用现成的工具；</li>
<li>缺点：<ul>
<li>由于需要扫描整个 <code>keyspace</code>，实时性上比较差;</li>
<li>扫描时间与 <code>key</code> 的数量正相关，如果 <code>key</code> 的数量比较多，耗时可能会非常长。</li>
</ul>
</li>
</ul>
<blockquote>
<p>hotkeys<br><a target="_blank" rel="noopener" href="https://www.zhangbj.com/p/765.html">https://www.zhangbj.com/p/765.html</a></p>
</blockquote>
<ol start="2">
<li><a target="_blank" rel="noopener" href="https://redis.io/commands/monitor">monitor</a> 命令</li>
</ol>
<p><code>monitor</code> 命令可以实时抓取出 <code>Redis</code> 服务器接收到的命令，通过 <code>redis-cli monitor</code> 抓取数据，同时结合一些现成的分析工具，比如 <a target="_blank" rel="noopener" href="https://github.com/facebookarchive/redis-faina">redis-faina</a>，统计出热 Key。</p>
<ul>
<li>优点：无需进行二次开发，能够直接利用现成的工具；</li>
<li>缺点：该命令在高并发的条件下，有内存增暴增的隐患，还会降低 <code>Redis</code> 的性能。</li>
</ul>
<h3 id="Redis-节点抓包分析"><a href="#Redis-节点抓包分析" class="headerlink" title="Redis 节点抓包分析"></a>Redis 节点抓包分析</h3><p><code>Redis</code> 客户端使用 <code>TCP</code> 协议与服务端进行交互，通信协议采用的是 <code>RESP</code> 协议。自己写程序监听端口，按照 <code>RESP</code> 协议规则解析数据，进行分析。或者我们可以使用一些抓包工具，比如 <code>tcpdump</code> 工具，抓取一段时间内的流量进行解析。</p>
<ul>
<li>优点：对 <code>SDK</code> 或者 <code>Proxy</code> 代理层没有入侵；</li>
<li>缺点：<ul>
<li>有一定的开发成本；</li>
<li>热 <code>Key</code> 节点的网络流量和系统负载已经比较高了，抓包可能会导致情况进一步恶化。</li>
</ul>
</li>
</ul>
<h2 id="如何解决"><a href="#如何解决" class="headerlink" title="如何解决"></a>如何解决</h2><h3 id="增加-Redis-实例副本数量"><a href="#增加-Redis-实例副本数量" class="headerlink" title="增加 Redis 实例副本数量"></a>增加 Redis 实例副本数量</h3><p>对于出现热 <code>Key</code> 的 <code>Redis</code> 实例，我们可以通过水平扩容增加副本数量，将读请求的压力分担到不同副本节点上。</p>
<p>(通过<strong>主从复制-读写分离</strong>，将读请求分散多个机器上。)</p>
<h3 id="二级缓存（本地缓存）"><a href="#二级缓存（本地缓存）" class="headerlink" title="二级缓存（本地缓存）"></a>二级缓存（本地缓存）</h3><p>当出现热 <code>Key</code> 以后，把热 <code>Key</code> 加载到系统的 <code>JVM</code> 中。后续针对这些热 <code>Key</code> 的请求，会直接从 <code>JVM</code> 中获取，而不会走到 <code>Redis</code> 层。这些本地缓存的工具很多，比如 <code>Ehcache</code>，或者 <code>Google Guava</code> 中 <code>Cache</code> 工具，或者直接使用 <code>HashMap</code> 作为本地缓存工具都是可以的。</p>
<p><strong>使用本地缓存需要注意两个问题：</strong></p>
<ul>
<li>如果对热 <code>Key</code> 进行本地缓存，需要防止本地缓存过大，影响系统性能；</li>
<li>需要处理本地缓存和 <code>Redis</code> 集群数据的一致性问题。</li>
</ul>
<h3 id="热-Key-备份"><a href="#热-Key-备份" class="headerlink" title="热 Key 备份"></a>热 Key 备份</h3><p>通过前面的分析，我们可以了解到，之所以出现热 <code>Key</code>，是因为有大量的对同一个 <code>Key</code> 的请求落到同一个 <code>Redis</code> 实例上，如果我们可以有办法将这些请求打散到不同的实例上，防止出现流量倾斜的情况，那么热 <code>Key</code> 问题也就不存在了。</p>
<p>那么如何将对某个热 <code>Key</code> 的请求打散到不同实例上呢？我们就可以通过热 <code>Key</code> 备份的方式，基本的思路就是，我们<strong>可以给热 <code>Key</code> 加上前缀或者后缀，把一个热 <code>Key</code> 的数量变成 <code>Redis</code> 实例个数 <code>N</code> 的倍数 <code>M</code>，从而由访问一个 <code>Redis</code> <code>Key</code> 变成访问 <code>N * M</code> 个 <code>Redis</code> <code>Key</code>。 <code>N * M</code> 个 <code>Redis</code> <code>Key</code> 经过分片分布到不同的实例上，将访问量均摊到所有实例</strong>。</p>
<p>具体的逻辑：</p>
<figure class="highlight lua"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line">// N 为 Redis 实例个数，M 为 N 的 <span class="number">2</span>倍</span><br><span class="line">const M = N * <span class="number">2</span></span><br><span class="line">//生成随机数</span><br><span class="line"><span class="built_in">random</span> = GenRandom(<span class="number">0</span>, M)</span><br><span class="line">//构造备份新 Key</span><br><span class="line">bakHotKey = hotKey + <span class="string">&quot;_&quot;</span> + <span class="built_in">random</span></span><br><span class="line">// 先从备份key中取</span><br><span class="line">data = redis.GET(bakHotKey)</span><br><span class="line"><span class="keyword">if</span> data == NULL &#123;</span><br><span class="line">    data = redis.GET(hotKey)</span><br><span class="line">    <span class="keyword">if</span> data == NULL &#123;</span><br><span class="line">        data = GetFromDB()</span><br><span class="line">        // 可以利用原子锁来写入数据保证数据一致性</span><br><span class="line">        redis.SET(hotKey, data, expireTime)</span><br><span class="line">        redis.SET(bakHotKey, data, expireTime + GenRandom(<span class="number">0</span>, <span class="number">5</span>))</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">        redis.SET(bakHotKey, data, expireTime + GenRandom(<span class="number">0</span>, <span class="number">5</span>))</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<p>在这段代码中，通过一个大于等于 <code>1</code> 小于 <code>M</code> 的随机数，得到一个 <code>bakHotKey</code>，程序会优先访问 <code>bakHotKey</code>，在得不到数据的情况下，再访问原来的 <code>hotkey</code>，并将 <code>hotkey</code> 的内容写回 <code>bakHotKey</code>。</p>
<p>值得注意的是，<code>backHotKey</code> 的过期时间是 <code>hotkey</code> 的过期时间加上一个较小的随机正整数，这是通过坡度过期的方式，保证在 <code>hotkey</code> 过期时，所有 <code>backHotKey</code> 不会同时过期而造成缓存雪崩。</p>
<blockquote>
<p>参考博客</p>
</blockquote>

      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="http://example.com/2022/08/12/%E9%9D%A2%E8%AF%95%E5%9C%BA%E6%99%AF%E7%AE%97%E6%B3%95%E9%A2%98/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="SongyangJi">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="JsyBlog">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="undefined | JsyBlog">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2022/08/12/%E9%9D%A2%E8%AF%95%E5%9C%BA%E6%99%AF%E7%AE%97%E6%B3%95%E9%A2%98/" class="post-title-link" itemprop="url">面试场景算法</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2022-08-12 10:47:21" itemprop="dateCreated datePublished" datetime="2022-08-12T10:47:21+08:00">2022-08-12</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar-check"></i>
      </span>
      <span class="post-meta-item-text">更新于</span>
      <time title="修改时间：2023-01-09 00:18:03" itemprop="dateModified" datetime="2023-01-09T00:18:03+08:00">2023-01-09</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E5%B7%A5%E7%A8%8B%E5%90%91%E7%AE%97%E6%B3%95/" itemprop="url" rel="index"><span itemprop="name">工程向算法</span></a>
        </span>
    </span>

  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <h2 id="SP1-某云ES倒排索引"><a href="#SP1-某云ES倒排索引" class="headerlink" title="SP1 某云ES倒排索引"></a>SP1 某云ES倒排索引</h2><p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/7ba676741a3c4920b7846476be520779?tpId=332&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=/exam/oj?page=1&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=332">https://www.nowcoder.com/practice/7ba676741a3c4920b7846476be520779?tpId=332&amp;tags=&amp;title=&amp;difficulty=0&amp;judgeStatus=0&amp;rp=0&amp;sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D332</a></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> java.util.*;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> ID      int整型ArrayList</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> content string字符串ArrayList</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> word    string字符串</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> int整型ArrayList</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">public</span> ArrayList&lt;Integer&gt; <span class="title function_">invertedIndex</span><span class="params">(ArrayList&lt;Integer&gt; ID, ArrayList&lt;String&gt; content, String word)</span> &#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        HashMap&lt;String, LinkedHashSet&lt;Integer&gt;&gt; map = <span class="keyword">new</span> <span class="title class_">HashMap</span>&lt;&gt;();</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; ID.size(); i++) &#123;</span><br><span class="line">            String[] split = content.get(i).split(<span class="string">&quot; &quot;</span>);</span><br><span class="line">            <span class="keyword">for</span> (String s : split) &#123;</span><br><span class="line">                LinkedHashSet&lt;Integer&gt; linkedHashSet = map.getOrDefault(s, <span class="keyword">new</span> <span class="title class_">LinkedHashSet</span>&lt;&gt;());</span><br><span class="line">                linkedHashSet.add(ID.get(i));</span><br><span class="line">                map.put(s, linkedHashSet);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> <span class="title class_">ArrayList</span>&lt;&gt;(map.getOrDefault(word, <span class="keyword">new</span> <span class="title class_">LinkedHashSet</span>&lt;&gt;()));</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<p><a target="_blank" rel="noopener" href="https://zh.m.wikipedia.org/zh/%E5%80%92%E6%8E%92%E7%B4%A2%E5%BC%95">倒排索引wiki</a></p>
<h2 id="SP4-某音一致性哈希"><a href="#SP4-某音一致性哈希" class="headerlink" title="SP4 某音一致性哈希"></a><strong>SP4</strong> <strong>某音一致性哈希</strong></h2><p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/a93bd04c71d445c090565da14990a421?tpId=332&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=/exam/oj?page=1&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=332">https://www.nowcoder.com/practice/a93bd04c71d445c090565da14990a421?tpId=332&amp;tags=&amp;title=&amp;difficulty=0&amp;judgeStatus=0&amp;rp=0&amp;sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D332</a></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> java.util.*;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">ConsistentHashing</span> &#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="type">static</span> <span class="keyword">class</span> <span class="title class_">Section</span> &#123;</span><br><span class="line">        <span class="type">int</span> id;</span><br><span class="line">        <span class="type">int</span> l, r;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Section</span><span class="params">(<span class="type">int</span> l, <span class="type">int</span> r)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">this</span>.l = l;</span><br><span class="line">            <span class="keyword">this</span>.r = r;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Section</span><span class="params">(<span class="type">int</span> id, <span class="type">int</span> l, <span class="type">int</span> r)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">this</span>.id = id;</span><br><span class="line">            <span class="keyword">this</span>.l = l;</span><br><span class="line">            <span class="keyword">this</span>.r = r;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        @<span class="function">Override</span></span><br><span class="line"><span class="function">        <span class="keyword">public</span> String <span class="title">toString</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="string">&quot;&#123;&quot;</span> +</span><br><span class="line">                    <span class="string">&quot;id=&quot;</span> + id +</span><br><span class="line">                    <span class="string">&quot;, l=&quot;</span> + l +</span><br><span class="line">                    <span class="string">&quot;, r=&quot;</span> + r +</span><br><span class="line">                    <span class="string">&#x27;&#125;&#x27;</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="type">int</span> machineId = <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="type">int</span> <span class="title">nextMachineId</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> machineId++;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    PriorityQueue&lt;Section&gt; sectionLengthPQ;</span><br><span class="line">    TreeSet&lt;Section&gt; lSet;</span><br><span class="line"></span><br><span class="line">    <span class="type">int</span> capacity;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">ConsistentHashing</span><span class="params">(<span class="type">int</span> capacity)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.capacity = capacity;</span><br><span class="line">        <span class="built_in">init</span>();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">void</span> <span class="title">init</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        sectionLengthPQ = <span class="keyword">new</span> PriorityQueue&lt;&gt;(<span class="keyword">new</span> <span class="built_in">Comparator</span>&lt;Section&gt;() &#123;</span><br><span class="line">            @Override</span><br><span class="line">            <span class="keyword">public</span> <span class="type">int</span> <span class="built_in">compare</span>(Section o1, Section o2) &#123;</span><br><span class="line">                <span class="type">int</span> cmp = (o2.r - o2.l) - (o1.r - o1.l);</span><br><span class="line">                <span class="keyword">if</span> (cmp != <span class="number">0</span>) <span class="keyword">return</span> cmp;</span><br><span class="line">                <span class="keyword">return</span> o1.id - o2.id;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;);</span><br><span class="line">        lSet = <span class="keyword">new</span> TreeSet&lt;&gt;(Comparator.<span class="built_in">comparingInt</span>(o -&gt; o.l));</span><br><span class="line">        Section section = <span class="keyword">new</span> <span class="built_in">Section</span>(<span class="built_in">nextMachineId</span>(), <span class="number">0</span>, <span class="keyword">this</span>.capacity - <span class="number">1</span>);</span><br><span class="line">        sectionLengthPQ.<span class="built_in">offer</span>(section);</span><br><span class="line">        lSet.<span class="built_in">add</span>(section);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="type">void</span> <span class="title">addNode</span><span class="params">(<span class="type">int</span> n)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">            Section section = sectionLengthPQ.<span class="built_in">poll</span>();</span><br><span class="line">            <span class="type">int</span> oldId = section.id;</span><br><span class="line">            <span class="type">int</span> newId = <span class="built_in">nextMachineId</span>();</span><br><span class="line">            <span class="type">int</span> l = section.l;</span><br><span class="line">            <span class="type">int</span> r = section.r;</span><br><span class="line">            lSet.<span class="built_in">remove</span>(section);</span><br><span class="line">            <span class="type">int</span> l1 = l, r1 = (r - l) / <span class="number">2</span> + l;</span><br><span class="line">            <span class="type">int</span> l2 = r1 + <span class="number">1</span>, r2 = r;</span><br><span class="line">            Section section1 = <span class="keyword">new</span> <span class="built_in">Section</span>(oldId, l1, r1);</span><br><span class="line">            Section section2 = <span class="keyword">new</span> <span class="built_in">Section</span>(newId, l2, r2);</span><br><span class="line">            sectionLengthPQ.<span class="built_in">offer</span>(section1);</span><br><span class="line">            sectionLengthPQ.<span class="built_in">offer</span>(section2);</span><br><span class="line">            lSet.<span class="built_in">add</span>(section1);</span><br><span class="line">            lSet.<span class="built_in">add</span>(section2);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="type">int</span> <span class="title">querySection</span><span class="params">(<span class="type">int</span> ID)</span> </span>&#123;</span><br><span class="line">        <span class="type">int</span> id = ID % capacity;</span><br><span class="line">        Section section = <span class="keyword">new</span> <span class="built_in">Section</span>(id, id);</span><br><span class="line">        <span class="keyword">return</span> lSet.<span class="built_in">floor</span>(section).id;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * @param n  int整型</span></span><br><span class="line"><span class="comment">     * @param ID int整型</span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="type">int</span> <span class="title">consistentHashing</span><span class="params">(<span class="type">int</span> n, <span class="type">int</span> ID)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        ConsistentHashing consistentHashing = <span class="keyword">new</span> <span class="built_in">ConsistentHashing</span>(<span class="number">800</span>);</span><br><span class="line">        consistentHashing.<span class="built_in">addNode</span>(n - <span class="number">1</span>);</span><br><span class="line">        <span class="keyword">return</span> consistentHashing.<span class="built_in">querySection</span>(ID);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="type">static</span> <span class="type">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line">        Solution solution = <span class="keyword">new</span> <span class="built_in">Solution</span>();</span><br><span class="line">        System.out.<span class="built_in">println</span>(solution.<span class="built_in">consistentHashing</span>(<span class="number">10</span>, <span class="number">999</span>));</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><a target="_blank" rel="noopener" href="https://zh.wikipedia.org/wiki/%E4%B8%80%E8%87%B4%E5%93%88%E5%B8%8C">一致哈希</a></p>
<p><a target="_blank" rel="noopener" href="https://segmentfault.com/a/1190000021199728">https://segmentfault.com/a/1190000021199728</a></p>
<p><a target="_blank" rel="noopener" href="https://zhuanlan.zhihu.com/p/378056811">https://zhuanlan.zhihu.com/p/378056811</a></p>

      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="http://example.com/2022/08/12/%E5%80%92%E6%8E%92%E7%B4%A2%E5%BC%95/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="SongyangJi">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="JsyBlog">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="undefined | JsyBlog">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2022/08/12/%E5%80%92%E6%8E%92%E7%B4%A2%E5%BC%95/" class="post-title-link" itemprop="url">倒排索引</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2022-08-12 10:23:03" itemprop="dateCreated datePublished" datetime="2022-08-12T10:23:03+08:00">2022-08-12</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar-check"></i>
      </span>
      <span class="post-meta-item-text">更新于</span>
      <time title="修改时间：2022-09-02 22:44:06" itemprop="dateModified" datetime="2022-09-02T22:44:06+08:00">2022-09-02</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" itemprop="url" rel="index"><span itemprop="name">数据结构</span></a>
        </span>
    </span>

  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <blockquote>
<p>正向索引：存储每个文档的单词的列表。</p>
<p>正向索引的查询往往满足每个文档有序频繁的全文查询。</p>
</blockquote>
<h1 id="倒排索引"><a href="#倒排索引" class="headerlink" title="倒排索引"></a>倒排索引</h1><blockquote>
<p>反向索引数据结构是典型的<a target="_blank" rel="noopener" href="https://zh.m.wikipedia.org/wiki/%E6%90%9C%E7%B4%A2%E5%BC%95%E6%93%8E">搜索引擎</a><a target="_blank" rel="noopener" href="https://zh.m.wikipedia.org/wiki/%E6%AA%A2%E7%B4%A2">检索</a><a target="_blank" rel="noopener" href="https://zh.m.wikipedia.org/wiki/%E7%AE%97%E6%B3%95">算法</a>重要的部分。</p>
</blockquote>
<p><strong>倒排索引</strong>（英语：Inverted index），也常被称为<strong>反向索引</strong>、<strong>置入档案</strong>或<strong>反向档案</strong>，是一种索引方法，被<strong>用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射</strong>。它是<em>文档检索系统</em>中最常用的数据结构。</p>
<p>有两种不同的反向索引形式：</p>
<ul>
<li>一条记录的水平反向索引（或者<strong>反向档案索引</strong>）包含每个引用单词的文档的[列表]。</li>
<li>一个单词的水平反向索引（或者<strong>完全反向索引</strong>）又包含每个单词在一个文档中的位置。</li>
</ul>
<p>后者的形式提供了更多的兼容性（比如<em>短语搜索</em>），但是需要更多的时间和空间来创建。</p>
<p>举例，下面是要被索引的文本：</p>
<ul><li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{0}=}">
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <msub>
          <mi>T</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mn>0</mn>
          </mrow>
        </msub>
        <mo>=</mo>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle T_{0}=}</annotation>
  </semantics></math></span><noscript><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1ab3d9202f18a678affe9a339511bef0a7b8b110" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.671ex; width:4.865ex; height:2.509ex;" alt="{\displaystyle T_{0}=}"></noscript><img width="0" height="0" class="mwe-math-fallback-image-inline image-lazy-loaded" alt="{\displaystyle T_{0}=}" usemap="undefined" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1ab3d9202f18a678affe9a339511bef0a7b8b110" srcset="" style="width: 4.865ex; height: 2.509ex; vertical-align: -0.671ex;"></span><code>0. "it is what it is"</code></li>
<li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}=}">
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <msub>
          <mi>T</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mn>1</mn>
          </mrow>
        </msub>
        <mo>=</mo>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle T_{1}=}</annotation>
  </semantics></math></span><noscript><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/57ac5840245616f79874f4635b3bcb2e3da344dd" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.671ex; width:4.865ex; height:2.509ex;" alt="{\displaystyle T_{1}=}"></noscript><img width="0" height="0" class="mwe-math-fallback-image-inline image-lazy-loaded" alt="{\displaystyle T_{1}=}" usemap="undefined" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/57ac5840245616f79874f4635b3bcb2e3da344dd" srcset="" style="width: 4.865ex; height: 2.509ex; vertical-align: -0.671ex;"></span><code>1. "what is it"</code></li>
<li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}=}">
  <semantics>
    <mrow class="MJX-TeXAtom-ORD">
      <mstyle displaystyle="true" scriptlevel="0">
        <msub>
          <mi>T</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mn>2</mn>
          </mrow>
        </msub>
        <mo>=</mo>
      </mstyle>
    </mrow>
    <annotation encoding="application/x-tex">{\displaystyle T_{2}=}</annotation>
  </semantics></math></span><noscript><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5713cf5634b3846b4d68c3383b65db289511d8bf" class="mwe-math-fallback-image-inline" aria-hidden="true" style="vertical-align: -0.671ex; width:4.865ex; height:2.509ex;" alt="{\displaystyle T_{2}=}"></noscript><img width="0" height="0" class="mwe-math-fallback-image-inline image-lazy-loaded" alt="{\displaystyle T_{2}=}" usemap="undefined" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5713cf5634b3846b4d68c3383b65db289511d8bf" srcset="" style="width: 4.865ex; height: 2.509ex; vertical-align: -0.671ex;"></span><code>2. "it is a banana"</code></li></ul>



<h2 id="反向档案索引"><a href="#反向档案索引" class="headerlink" title="反向档案索引"></a>反向档案索引</h2><p>我们就能得到下面的反向文件索引：</p>
<pre> "a":      {2}
 "banana": {2}
 "is":     {0, 1, 2}
 "it":     {0, 1, 2}
 "what":   {0, 1}
</pre>
<p>如果要检索 ‘what’、’is’、’it’将对应这个集合：<br>$$<br>{0,1}\cap{0,1,2}\cap{0,1,2}&#x3D;{0,1}<br>$$</p>
<h2 id="完全反向索引"><a href="#完全反向索引" class="headerlink" title="完全反向索引"></a>完全反向索引</h2><p>对相同的文字，我们得到后面这些完全反向索引，由文档数量和当前查询的单词结果组成的的成对数据。 同样，文档数量和当前查询的单词结果都从零开始。所以，”banana”: {(2, 3)} 就是说 “banana”在第三个文档里 T2，而且在第三个文档的位置是第四个单词(地址为 3)。</p>
<pre>"a":      {(2, 2)}
"banana": {(2, 3)}
"is":     {(0, 1), (0, 4), <b>(1, 1)</b>, (2, 1)}
"it":     {(0, 0), (0, 3), <b>(1, 2)</b>, (2, 0)} 
"what":   {(0, 2), <b>(1, 0)</b>}
</pre>


<p>如果我们执行短语搜索<code>&quot;what is it&quot;</code> 我们得到这个短语的全部单词各自的结果所在文档为文档0和文档1。但是这个短语检索的连续的条件仅仅在文档1得到。</p>

      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="http://example.com/2022/07/26/JUnit%E5%92%8CMockito/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="SongyangJi">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="JsyBlog">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="undefined | JsyBlog">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2022/07/26/JUnit%E5%92%8CMockito/" class="post-title-link" itemprop="url">JUnit和Mockito</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2022-07-26 02:03:06" itemprop="dateCreated datePublished" datetime="2022-07-26T02:03:06+08:00">2022-07-26</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar-check"></i>
      </span>
      <span class="post-meta-item-text">更新于</span>
      <time title="修改时间：2022-09-02 22:44:06" itemprop="dateModified" datetime="2022-09-02T22:44:06+08:00">2022-09-02</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E6%B5%8B%E8%AF%95/" itemprop="url" rel="index"><span itemprop="name">测试</span></a>
        </span>
    </span>

  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <blockquote>
<p><a target="_blank" rel="noopener" href="https://www.cnblogs.com/Ming8006/p/6297333.html">教程</a><br><a target="_blank" rel="noopener" href="https://site.mockito.org/">官网</a><br><a target="_blank" rel="noopener" href="https://stackoverflow.com/questions/36615330/mockito-doanswer-vs-thenreturn">thenAnswer VS thenReturn</a><br><a target="_blank" rel="noopener" href="https://blog.csdn.net/blueZhangFun/article/details/103665393">verify用法</a><br><a target="_blank" rel="noopener" href="https://breeze924.github.io/2018/08/26/JUnit%E7%9F%A5%E8%AF%86%E7%82%B9%E4%B8%89%E5%88%99/">@Mock和@InjectMocks的区别</a><br><a target="_blank" rel="noopener" href="https://www.cnblogs.com/hezhiyao/p/9440277.html">@Before、@After、@Test</a></p>
</blockquote>

      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="http://example.com/2022/07/20/%E4%B8%80%E4%BA%9B%E8%BF%98%E4%B8%8D%E9%94%99%E7%9A%84%E9%A2%98-4/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="SongyangJi">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="JsyBlog">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="undefined | JsyBlog">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2022/07/20/%E4%B8%80%E4%BA%9B%E8%BF%98%E4%B8%8D%E9%94%99%E7%9A%84%E9%A2%98-4/" class="post-title-link" itemprop="url">一些还不错的题-4</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2022-07-20 00:00:03" itemprop="dateCreated datePublished" datetime="2022-07-20T00:00:03+08:00">2022-07-20</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar-check"></i>
      </span>
      <span class="post-meta-item-text">更新于</span>
      <time title="修改时间：2023-01-03 19:25:56" itemprop="dateModified" datetime="2023-01-03T19:25:56+08:00">2023-01-03</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/%E7%AE%97%E6%B3%95%E9%A2%98/" itemprop="url" rel="index"><span itemprop="name">算法题</span></a>
        </span>
    </span>

  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <h2 id="二叉树"><a href="#二叉树" class="headerlink" title="二叉树"></a>二叉树</h2><h3 id="二叉树第K小"><a href="#二叉树第K小" class="headerlink" title="二叉树第K小"></a>二叉树第K小</h3><p>给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。</p>
<p>1.返回第k小的节点值即可</p>
<p>2.不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1</p>
<p>3.保证n个节点的值不一样</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>: </span><br><span class="line">    <span class="type">int</span> cnt = <span class="number">0</span>;</span><br><span class="line">    <span class="type">int</span> ans = <span class="number">-1</span>;</span><br><span class="line">    <span class="type">int</span> k;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">KthNode</span><span class="params">(TreeNode* proot, <span class="type">int</span> k)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(proot == <span class="literal">nullptr</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">this</span>-&gt;k = k;</span><br><span class="line">        <span class="built_in">dfs</span>(proot);</span><br><span class="line">        <span class="keyword">return</span> ans;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="type">void</span> <span class="title">dfs</span><span class="params">(TreeNode* root)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(root == <span class="literal">nullptr</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">dfs</span>(root-&gt;left);</span><br><span class="line">        ++cnt;</span><br><span class="line">        <span class="keyword">if</span>(cnt == k) &#123;</span><br><span class="line">            ans = root-&gt;val;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">dfs</span>(root-&gt;right);</span><br><span class="line">    &#125;</span><br><span class="line">        </span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>





<h2 id="DP"><a href="#DP" class="headerlink" title="DP"></a>DP</h2><h3 id="扔鸡蛋"><a href="#扔鸡蛋" class="headerlink" title="扔鸡蛋"></a>扔鸡蛋</h3><p>时间复杂度：O(nk)&#x3D;O(nlogn)</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">define</span> inf 0x3f3f3f3f</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     * 返回最差情况下扔棋子的最小次数</span></span><br><span class="line"><span class="comment">     * @param n int整型 楼层数</span></span><br><span class="line"><span class="comment">     * @param k int整型 棋子数</span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">    状态：f[i][j] i个棋子，j层楼的操作系数</span></span><br><span class="line"><span class="comment">    转移：f[i][j] = 1 + max(f[i - 1][t - 1], f[i][j - t]) 枚举所有的t，找出最优的</span></span><br><span class="line"><span class="comment">    初始：f[1][j] = j;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">    空间优化，i的维度只用到当前状态和前一个状态，所有可以使用滚动数组优化成f[j]</span></span><br><span class="line"><span class="comment">    时间优化，i确定的时候，f[i - 1][t - 1]随t单调增，f[i][j - t]随t单调减，临界点的寻找可以用单调性优化</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">    */</span></span><br><span class="line"></span><br><span class="line">    <span class="type">const</span> <span class="type">int</span> N = <span class="number">1000010</span>;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">solve</span><span class="params">(<span class="type">int</span> n, <span class="type">int</span> k)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 优化性质, 如果k充分大, 二分的扔即可（有点投机取巧）</span></span><br><span class="line">        <span class="type">int</span> b = <span class="built_in">log2</span>(n) + <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">if</span>(k &gt;= <span class="built_in">log2</span>(n) + <span class="number">1</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> b;</span><br><span class="line">        &#125;</span><br><span class="line">        k = <span class="built_in">min</span>(k, n);</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        <span class="function">vector&lt;<span class="type">int</span>&gt; <span class="title">f0</span><span class="params">(N)</span>, <span class="title">f1</span><span class="params">(N)</span></span>;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 初始化</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt;= n; ++j) &#123;</span><br><span class="line">            f0[j] = j;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">2</span>; i &lt;= k; ++i) &#123;</span><br><span class="line">            <span class="type">int</span> tt = <span class="number">1</span>; <span class="comment">// 临界点逐渐递增</span></span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">1</span>; j &lt;= n; j++) &#123;</span><br><span class="line">                <span class="type">int</span> res = inf;</span><br><span class="line"><span class="comment">//                原始版本                </span></span><br><span class="line"><span class="comment">//                for(int t = j; t &gt;= tt; --t) &#123;</span></span><br><span class="line"><span class="comment">//                    res = min(res, max(f0[t - 1], f1[j - t]) + 1);</span></span><br><span class="line"><span class="comment">//                &#125;</span></span><br><span class="line">                <span class="keyword">while</span> (tt &lt;= j &amp;&amp; f0[tt - <span class="number">1</span>] &lt; f1[j - tt]) &#123;</span><br><span class="line">                    ++tt;</span><br><span class="line">                &#125;</span><br><span class="line">                res = f1[j - (tt - <span class="number">1</span>)];</span><br><span class="line">                <span class="keyword">if</span>(tt &lt;= j) res = <span class="built_in">min</span>(res, f0[tt - <span class="number">1</span>]);</span><br><span class="line">                f1[j] = res + <span class="number">1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            f0 = f1;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> f0[n];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br></pre></td></tr></table></figure>


<blockquote>
<p>题解</p>
<p><a target="_blank" rel="noopener" href="https://song-yang-ji.blog.csdn.net/article/details/121206001">https://song-yang-ji.blog.csdn.net/article/details/121206001</a></p>
<p><a target="_blank" rel="noopener" href="https://blog.nowcoder.net/n/702aa052fefb4b7d8e2949874c52316a?f=comment">https://blog.nowcoder.net/n/702aa052fefb4b7d8e2949874c52316a?f=comment</a></p>
</blockquote>
<h3 id="NC122-正则表达式匹配"><a href="#NC122-正则表达式匹配" class="headerlink" title="NC122 正则表达式匹配"></a>NC122 正则表达式匹配</h3><p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4?tpId=117&tqId=37780&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=50&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4?tpId=117&amp;tqId=37780&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * @param str string字符串</span></span><br><span class="line"><span class="comment">     * @param pattern string字符串</span></span><br><span class="line"><span class="comment">     * @return bool布尔型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">bool</span> <span class="title">match</span><span class="params">(string s, string p)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (p[<span class="number">0</span>] == <span class="string">&#x27;*&#x27;</span>) &#123; <span class="comment">// assert</span></span><br><span class="line">            <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="type">int</span> m = s.<span class="built_in">length</span>();</span><br><span class="line">        <span class="type">int</span> n = p.<span class="built_in">length</span>();</span><br><span class="line">        s = <span class="string">&quot; &quot;</span> + s;</span><br><span class="line">        p = <span class="string">&quot; &quot;</span> + p;</span><br><span class="line">        vector&lt;vector&lt;<span class="type">bool</span>&gt; &gt; <span class="built_in">f</span>(m + <span class="number">10</span>, <span class="built_in">vector</span>&lt;<span class="type">bool</span>&gt;(n + <span class="number">10</span>));</span><br><span class="line">        f[<span class="number">0</span>][<span class="number">0</span>] = <span class="literal">true</span>;</span><br><span class="line">        <span class="comment">// key: i start from 0</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt;= m; ++i) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">1</span>; j &lt;= n; ++j) &#123;</span><br><span class="line">                <span class="keyword">if</span> (p[j] == <span class="string">&#x27;*&#x27;</span>) &#123; <span class="comment">// assert j &gt;= 2</span></span><br><span class="line">                    <span class="type">char</span> c = p[j - <span class="number">1</span>];</span><br><span class="line">                    <span class="keyword">if</span> (f[i][j - <span class="number">2</span>]) &#123; <span class="comment">// 一次不用</span></span><br><span class="line">                        f[i][j] = <span class="literal">true</span>;</span><br><span class="line">                    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                        <span class="type">int</span> k = <span class="number">0</span>;</span><br><span class="line">                        <span class="keyword">while</span> (i &gt; k &amp;&amp; (c == <span class="string">&#x27;.&#x27;</span> || s[i - k] == c)) &#123;</span><br><span class="line">                            <span class="keyword">if</span> (f[i - k - <span class="number">1</span>][j - <span class="number">2</span>]) &#123;</span><br><span class="line">                                f[i][j] = <span class="literal">true</span>;</span><br><span class="line">                                <span class="keyword">break</span>;</span><br><span class="line">                            &#125;</span><br><span class="line">                            ++k;</span><br><span class="line">                        &#125;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                    <span class="keyword">if</span> (i &gt; <span class="number">0</span> &amp;&amp; f[i - <span class="number">1</span>][j - <span class="number">1</span>] &amp;&amp; (s[i] == p[j] || p[j] == <span class="string">&#x27;.&#x27;</span>)) &#123;</span><br><span class="line">                        f[i][j] = <span class="literal">true</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> f[m][n];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>





<p>更优秀的写法：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="type">bool</span> f[<span class="number">30</span>][<span class="number">40</span>] = &#123;<span class="number">0</span>&#125;;</span><br><span class="line">    <span class="function"><span class="type">bool</span> <span class="title">isMatch</span><span class="params">(string s, string p)</span> </span>&#123;</span><br><span class="line">        <span class="type">int</span> m = s.<span class="built_in">size</span>(), n = p.<span class="built_in">size</span>();</span><br><span class="line">        s = <span class="string">&quot; &quot;</span> + s;</span><br><span class="line">        p = <span class="string">&quot; &quot;</span> + p;</span><br><span class="line">        f[<span class="number">0</span>][<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">auto</span> ok = [&amp;](<span class="type">int</span> i, <span class="type">int</span> j) &#123;</span><br><span class="line">            <span class="keyword">if</span>(i == <span class="number">0</span> || j == <span class="number">0</span>) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">            <span class="keyword">return</span> p[j] == <span class="string">&#x27;.&#x27;</span> || s[i] == p[j];</span><br><span class="line">        &#125;;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt;= m; i++) &#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">1</span>; j &lt;= n; j++) &#123;</span><br><span class="line">                <span class="keyword">if</span>(p[j] == <span class="string">&#x27;*&#x27;</span>) &#123;</span><br><span class="line">                    f[i][j] = f[i][j - <span class="number">2</span>]; <span class="comment">// 题给数据保证不越界</span></span><br><span class="line">                    <span class="keyword">if</span>(<span class="built_in">ok</span>(i, j - <span class="number">1</span>)) &#123;</span><br><span class="line">                        f[i][j] |= f[i - <span class="number">1</span>][j]; <span class="comment">// key</span></span><br><span class="line">                    &#125;</span><br><span class="line">                &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                    f[i][j] = <span class="built_in">ok</span>(i, j) ? f[i - <span class="number">1</span>][j - <span class="number">1</span>] : <span class="literal">false</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> f[m][n];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br></pre></td></tr></table></figure>





<blockquote>
<p>题解</p>
<p><a target="_blank" rel="noopener" href="https://song-yang-ji.blog.csdn.net/article/details/121688339">https://song-yang-ji.blog.csdn.net/article/details/121688339</a></p>
</blockquote>
<h3 id="NC135-买卖股票的最好时机-三"><a href="#NC135-买卖股票的最好时机-三" class="headerlink" title="NC135 买卖股票的最好时机(三)"></a>NC135 买卖股票的最好时机(三)</h3><p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/4892d3ff304a4880b7a89ba01f48daf9?tpId=117&tqId=37847&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=100&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/4892d3ff304a4880b7a89ba01f48daf9?tpId=117&amp;tqId=37847&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D100%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">100010</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> inf = <span class="number">0x3f3f3f3f</span>;</span><br><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     * 两次交易所能获得的最大收益</span></span><br><span class="line"><span class="comment">     * @param prices int整型vector 股票每一天的价格</span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">maxProfit</span><span class="params">(vector&lt;<span class="type">int</span>&gt;&amp; a)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        <span class="type">int</span> n = a.<span class="built_in">size</span>();</span><br><span class="line">        <span class="type">int</span> f[N][<span class="number">3</span>][<span class="number">2</span>] = &#123;<span class="number">0</span>&#125;;</span><br><span class="line">        <span class="comment">// 初始化</span></span><br><span class="line">        f[<span class="number">0</span>][<span class="number">0</span>][<span class="number">1</span>] = -a[<span class="number">0</span>];</span><br><span class="line">        f[<span class="number">0</span>][<span class="number">1</span>][<span class="number">0</span>] = -inf;</span><br><span class="line">        f[<span class="number">0</span>][<span class="number">1</span>][<span class="number">1</span>] = -inf;</span><br><span class="line">        f[<span class="number">0</span>][<span class="number">2</span>][<span class="number">0</span>] = -inf;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt; n; ++i) &#123;</span><br><span class="line">            f[i][<span class="number">0</span>][<span class="number">1</span>] = <span class="built_in">max</span>(f[i - <span class="number">1</span>][<span class="number">0</span>][<span class="number">1</span>], f[i - <span class="number">1</span>][<span class="number">0</span>][<span class="number">0</span>] - a[i]);</span><br><span class="line">            f[i][<span class="number">1</span>][<span class="number">0</span>] = <span class="built_in">max</span>(f[i - <span class="number">1</span>][<span class="number">1</span>][<span class="number">0</span>], f[i - <span class="number">1</span>][<span class="number">0</span>][<span class="number">1</span>] + a[i]);</span><br><span class="line">            f[i][<span class="number">1</span>][<span class="number">1</span>] = <span class="built_in">max</span>(f[i - <span class="number">1</span>][<span class="number">1</span>][<span class="number">1</span>], f[i - <span class="number">1</span>][<span class="number">1</span>][<span class="number">0</span>] - a[i]);</span><br><span class="line">            f[i][<span class="number">2</span>][<span class="number">0</span>] = <span class="built_in">max</span>(f[i - <span class="number">1</span>][<span class="number">2</span>][<span class="number">0</span>], f[i - <span class="number">1</span>][<span class="number">1</span>][<span class="number">1</span>] + a[i]);</span><br><span class="line">        &#125;</span><br><span class="line">        </span><br><span class="line">        <span class="type">int</span> ans = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; <span class="number">3</span>; ++i) &#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">0</span>; j &lt; <span class="number">2</span>; ++j) &#123;</span><br><span class="line">                ans = <span class="built_in">max</span>(ans, f[n - <span class="number">1</span>][i][j]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> ans;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<h3 id="NC167-买卖股票的最好时机-四"><a href="#NC167-买卖股票的最好时机-四" class="headerlink" title="NC167 买卖股票的最好时机(四)"></a><strong>NC167</strong> <strong>买卖股票的最好时机(四)</strong></h3><p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/1c583d416d504b80821fbe4cc20404f3?tpId=117&tqId=39309&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=100&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/1c583d416d504b80821fbe4cc20404f3?tpId=117&amp;tqId=39309&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D100%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">define</span> inf 0x3f3f3f3f</span></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * @param prices int整型vector</span></span><br><span class="line"><span class="comment">     * @param k int整型</span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">maxProfit</span><span class="params">(vector&lt;<span class="type">int</span>&gt; &amp;a, <span class="type">int</span> K)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        <span class="type">int</span> n = a.<span class="built_in">size</span>();</span><br><span class="line">        vector&lt;vector&lt;vector&lt;<span class="type">int</span>&gt;&gt;&gt; <span class="built_in">f</span>(n + <span class="number">10</span>, vector&lt;vector&lt;<span class="type">int</span>&gt;&gt;(K + <span class="number">1</span>, <span class="built_in">vector</span>&lt;<span class="type">int</span>&gt;(<span class="number">2</span>, -inf)));</span><br><span class="line">        <span class="comment">// init</span></span><br><span class="line">        f[<span class="number">0</span>][<span class="number">0</span>][<span class="number">0</span>] = <span class="number">0</span>;</span><br><span class="line">        f[<span class="number">0</span>][<span class="number">0</span>][<span class="number">1</span>] = -a[<span class="number">0</span>];</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt; n; ++i) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> k = <span class="number">0</span>; k &lt;= K; ++k) &#123;</span><br><span class="line">                f[i][k][<span class="number">0</span>] = <span class="built_in">max</span>(f[i - <span class="number">1</span>][k][<span class="number">0</span>], k &gt; <span class="number">0</span> ? (f[i - <span class="number">1</span>][k - <span class="number">1</span>][<span class="number">1</span>] + a[i]) : -inf);</span><br><span class="line">                f[i][k][<span class="number">1</span>] = <span class="built_in">max</span>(f[i - <span class="number">1</span>][k][<span class="number">1</span>], f[i - <span class="number">1</span>][k][<span class="number">0</span>] - a[i]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="type">int</span> ans = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt;= K; i++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; <span class="number">2</span>; j++) &#123;</span><br><span class="line">                ans = <span class="built_in">max</span>(ans, f[n - <span class="number">1</span>][i][j]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> ans;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>





<h3 id="NC44通配符匹配"><a href="#NC44通配符匹配" class="headerlink" title="NC44通配符匹配"></a>NC44通配符匹配</h3><p>时间复杂度：O(m*n)</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="type">bool</span> <span class="title">isMatch</span><span class="params">(<span class="type">const</span> <span class="type">char</span> *ps, <span class="type">const</span> <span class="type">char</span> *pp)</span> </span>&#123;</span><br><span class="line">        <span class="type">int</span> m = <span class="built_in">strlen</span>(ps);</span><br><span class="line">        <span class="type">int</span> n = <span class="built_in">strlen</span>(pp);</span><br><span class="line">        string s = <span class="string">&quot; &quot;</span> + <span class="built_in">string</span>(ps);</span><br><span class="line">        string p = <span class="string">&quot; &quot;</span> + <span class="built_in">string</span>(pp);</span><br><span class="line">        vector&lt;vector&lt;<span class="type">bool</span>&gt;&gt; <span class="built_in">f</span>(m + <span class="number">10</span>, <span class="built_in">vector</span>&lt;<span class="type">bool</span>&gt;(n + <span class="number">10</span>));</span><br><span class="line">        f[<span class="number">0</span>][<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt;= m; ++i) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">1</span>; j &lt;= n; ++j) &#123;</span><br><span class="line">                <span class="keyword">if</span> (p[j] == <span class="string">&#x27;*&#x27;</span>) &#123;</span><br><span class="line">                    f[i][j] = f[i][j - <span class="number">1</span>] || (i &gt; <span class="number">0</span> &amp;&amp; f[i - <span class="number">1</span>][j]);</span><br><span class="line">                &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                    <span class="keyword">if</span> (i &gt; <span class="number">0</span> &amp;&amp; (s[i] == p[j] || p[j] == <span class="string">&#x27;?&#x27;</span>)) &#123;</span><br><span class="line">                        f[i][j] = f[i - <span class="number">1</span>][j - <span class="number">1</span>];</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> f[m][n];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<p>todo:</p>
<p>空间复杂度 O(1)，时间复杂度 O(n)</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"></span><br></pre></td></tr></table></figure>





<h3 id="NC173-填充数组"><a href="#NC173-填充数组" class="headerlink" title="NC173 填充数组"></a><strong>NC173</strong> <strong>填充数组</strong></h3><p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/3e34d9ed0bbc4db68b6fbca20a62926d?tpId=117&tqId=39329&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=100&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/3e34d9ed0bbc4db68b6fbca20a62926d?tpId=117&amp;tqId=39329&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D100%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<p><strong>计数DP</strong></p>
<p>加法原理</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">const</span> <span class="type">int</span> MOD = <span class="number">1e9</span> + <span class="number">7</span>; </span><br><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * </span></span><br><span class="line"><span class="comment">     * @param a int整型vector </span></span><br><span class="line"><span class="comment">     * @param k int整型 </span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">FillArray</span><span class="params">(vector&lt;<span class="type">int</span>&gt;&amp; a, <span class="type">int</span> K)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        <span class="type">int</span> n = a.<span class="built_in">size</span>();</span><br><span class="line">        vector&lt;vector&lt;<span class="type">int</span>&gt;&gt; <span class="built_in">f</span>(n + <span class="number">10</span>, <span class="built_in">vector</span>&lt;<span class="type">int</span>&gt;(K + <span class="number">10</span>));</span><br><span class="line">        <span class="comment">// init</span></span><br><span class="line">        <span class="keyword">if</span>(a[<span class="number">0</span>]) &#123;</span><br><span class="line">            f[<span class="number">0</span>][a[<span class="number">0</span>]] = <span class="number">1</span>;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> k = <span class="number">1</span>; k &lt;= K; ++k) &#123;</span><br><span class="line">                f[<span class="number">0</span>][k] = <span class="number">1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt; n; ++i) &#123;</span><br><span class="line">            <span class="type">int</span> tmp = <span class="number">0</span>;</span><br><span class="line">            <span class="keyword">if</span>(a[i]) &#123;</span><br><span class="line">                <span class="keyword">for</span>(<span class="type">int</span> k = <span class="number">1</span>; k &lt;= a[i]; ++k) &#123;</span><br><span class="line">                    tmp = (tmp + f[i - <span class="number">1</span>][k]) % MOD;</span><br><span class="line">                &#125;</span><br><span class="line">                f[i][a[i]] = tmp;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="keyword">for</span>(<span class="type">int</span> k = <span class="number">1</span>; k &lt;= K; ++k) &#123;</span><br><span class="line">                    tmp = (tmp + f[i - <span class="number">1</span>][k]) % MOD;</span><br><span class="line">                    f[i][k] = tmp;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="type">int</span> ans = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> k = <span class="number">1</span>; k &lt;= K; ++k) &#123;</span><br><span class="line">            ans = (ans + f[n - <span class="number">1</span>][k]) % MOD;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> ans;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<h3 id="NC178-打家劫舍-三"><a href="#NC178-打家劫舍-三" class="headerlink" title="NC178 打家劫舍(三)"></a><strong>NC178</strong> <strong>打家劫舍(三)</strong></h3><p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/82b6dce6a7634419b272ee4397e26d89?tpId=117&tqId=39334&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=100&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/82b6dce6a7634419b272ee4397e26d89?tpId=117&amp;tqId=39334&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D100%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * @param root TreeNode类</span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    unordered_map&lt;TreeNode *, unordered_map&lt;<span class="type">bool</span>, <span class="type">int</span>&gt;&gt; dp;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">rob</span><span class="params">(TreeNode *root)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">max</span>(<span class="built_in">help</span>(root-&gt;left, <span class="literal">false</span>) + <span class="built_in">help</span>(root-&gt;right, <span class="literal">false</span>),</span><br><span class="line">                   root-&gt;val + <span class="built_in">help</span>(root-&gt;left, <span class="literal">true</span>) + <span class="built_in">help</span>(root-&gt;right, <span class="literal">true</span>));</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">help</span><span class="params">(TreeNode *root, <span class="type">bool</span> pick)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (root == <span class="literal">nullptr</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">if</span>(dp[root][pick]) <span class="keyword">return</span> dp[root][pick];</span><br><span class="line">        <span class="type">int</span> res = <span class="built_in">help</span>(root-&gt;left, <span class="literal">false</span>) + <span class="built_in">help</span>(root-&gt;right, <span class="literal">false</span>);</span><br><span class="line">        <span class="keyword">if</span> (!pick) &#123;</span><br><span class="line">            res = <span class="built_in">max</span>(res, root-&gt;val + <span class="built_in">help</span>(root-&gt;left, <span class="literal">true</span>) + <span class="built_in">help</span>(root-&gt;right, <span class="literal">true</span>));</span><br><span class="line">        &#125;</span><br><span class="line">        dp[root][pick] = res;</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<p>或者更好的：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    unordered_map&lt;TreeNode *, <span class="type">int</span>&gt; mp1, mp2;<span class="comment">//mp1,mp2分别表示当前节点偷或不偷的最大金额</span></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">rob</span><span class="params">(TreeNode *root)</span> </span>&#123;</span><br><span class="line">        <span class="built_in">f</span>(root);<span class="comment">//递归</span></span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">max</span>(mp1[root], mp2[root]);<span class="comment">//返回最大值</span></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">void</span> <span class="title">f</span><span class="params">(TreeNode *root)</span> </span>&#123;<span class="comment">//递归</span></span><br><span class="line">        <span class="keyword">if</span> (root == <span class="literal">nullptr</span>)</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        <span class="built_in">f</span>(root-&gt;left);<span class="comment">//左递归</span></span><br><span class="line">        <span class="built_in">f</span>(root-&gt;right);<span class="comment">//右递归</span></span><br><span class="line">        mp1[root] = root-&gt;val + mp2[root-&gt;left] + mp2[root-&gt;right];<span class="comment">//当前节点偷</span></span><br><span class="line">        mp2[root] = <span class="built_in">max</span>(mp1[root-&gt;left], mp2[root-&gt;left]) + <span class="built_in">max</span>(mp1[root-&gt;right], mp2[root-&gt;right]);<span class="comment">//当前节点不偷</span></span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>





<h3 id="NC196-编辑距离-一"><a href="#NC196-编辑距离-一" class="headerlink" title="NC196 编辑距离(一)"></a><strong>NC196</strong> <strong>编辑距离(一)</strong></h3><p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/6a1483b5be1547b1acd7940f867be0da?tpId=117&tqId=39371&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=100&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/6a1483b5be1547b1acd7940f867be0da?tpId=117&amp;tqId=39371&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D100%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">1010</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> INF = <span class="number">0x3f3f3f3f</span>;</span><br><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * </span></span><br><span class="line"><span class="comment">     * @param str1 string字符串 </span></span><br><span class="line"><span class="comment">     * @param str2 string字符串 </span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">editDistance</span><span class="params">(string s1, string s2)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        <span class="type">int</span> f[N][N];</span><br><span class="line">        <span class="built_in">memset</span>(f, INF, <span class="built_in">sizeof</span>(f));</span><br><span class="line">        <span class="type">int</span> m = s1.<span class="built_in">size</span>();</span><br><span class="line">        <span class="type">int</span> n = s2.<span class="built_in">size</span>();</span><br><span class="line">        s1 = <span class="string">&quot; &quot;</span> + s1;</span><br><span class="line">        s2 = <span class="string">&quot; &quot;</span> + s2;</span><br><span class="line">        f[<span class="number">0</span>][<span class="number">0</span>] = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">1</span>; j &lt;= n; ++j) &#123;</span><br><span class="line">            f[<span class="number">0</span>][j] = j; <span class="comment">// add</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= m; ++i) &#123;</span><br><span class="line">            f[i][<span class="number">0</span>] = i; <span class="comment">// del</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= m; ++i) &#123; <span class="comment">// key</span></span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">1</span>; j &lt;= n; ++j) &#123;</span><br><span class="line">                <span class="type">int</span> res = INF;</span><br><span class="line">                res = f[i - <span class="number">1</span>][j - <span class="number">1</span>] + ((s1[i] == s2[j]) ? <span class="number">0</span> : <span class="number">1</span>);</span><br><span class="line">                res = <span class="built_in">min</span>(res, f[i][j - <span class="number">1</span>] + <span class="number">1</span>); <span class="comment">// add</span></span><br><span class="line">                res = <span class="built_in">min</span>(res, f[i - <span class="number">1</span>][j] + <span class="number">1</span>); <span class="comment">// del</span></span><br><span class="line">                f[i][j] = res;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> f[m][n];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<h3 id="NC187-压缩字符串-二"><a href="#NC187-压缩字符串-二" class="headerlink" title="NC187 压缩字符串(二)"></a><strong>NC187</strong> <strong>压缩字符串(二)</strong></h3><p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/2724df81a7d94b70932d96b759848f0a?tpId=117&tqId=39354&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=100&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/2724df81a7d94b70932d96b759848f0a?tpId=117&amp;tqId=39354&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D100%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">define</span> inf 0x3f3f3f3f</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> ll long long</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> ull unsigned long long</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * @param s string字符串</span></span><br><span class="line"><span class="comment">     * @param k int整型</span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="type">int</span> f[<span class="number">110</span>][<span class="number">110</span>];</span><br><span class="line">    <span class="type">int</span> n;</span><br><span class="line">    string s;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">compressString</span><span class="params">(string s, <span class="type">int</span> k)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        n = s.<span class="built_in">length</span>();</span><br><span class="line">        <span class="keyword">this</span>-&gt;s = s;</span><br><span class="line">        <span class="keyword">if</span> (n == <span class="number">0</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        <span class="built_in">memset</span>(f, inf, <span class="keyword">sizeof</span> f);</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">dfs</span>(<span class="number">0</span>, k);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">trans</span><span class="params">(<span class="type">int</span> num)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (num == <span class="number">1</span>) <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">        string numStr = <span class="built_in">to_string</span>(num);</span><br><span class="line">        <span class="keyword">return</span> numStr.<span class="built_in">length</span>() + <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">dfs</span><span class="params">(<span class="type">int</span> idx, <span class="type">int</span> k)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (idx == n) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        <span class="type">int</span> &amp;res = f[idx][k];</span><br><span class="line">        <span class="keyword">if</span> (res != inf) <span class="keyword">return</span> res;</span><br><span class="line">        <span class="keyword">if</span> (k) res = <span class="built_in">dfs</span>(idx + <span class="number">1</span>, k - <span class="number">1</span>);</span><br><span class="line">        <span class="type">char</span> c = s[idx];</span><br><span class="line">        <span class="type">int</span> same = <span class="number">0</span>, diff = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = idx; i &lt; n; ++i) &#123;</span><br><span class="line">            <span class="keyword">if</span> (c == s[i]) &#123;</span><br><span class="line">                ++same;</span><br><span class="line">                res = <span class="built_in">min</span>(res, <span class="built_in">trans</span>(same) + <span class="built_in">dfs</span>(i + <span class="number">1</span>, k - diff));</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                res = <span class="built_in">min</span>(res, <span class="built_in">trans</span>(same) + <span class="built_in">dfs</span>(i, k - diff));</span><br><span class="line">                ++diff;</span><br><span class="line">                <span class="keyword">if</span> (diff &gt; k) <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">define</span> inf 0x3f3f3f3f</span></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * </span></span><br><span class="line"><span class="comment">     * @param s string字符串 </span></span><br><span class="line"><span class="comment">     * @param k int整型 </span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="type">int</span> f[<span class="number">110</span>][<span class="number">110</span>];</span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">compressString</span><span class="params">(string s, <span class="type">int</span> K)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        <span class="type">int</span> n = s.<span class="built_in">size</span>();</span><br><span class="line">        <span class="built_in">memset</span>(f, inf, <span class="built_in">sizeof</span>(f));</span><br><span class="line">        s = <span class="string">&quot; &quot;</span> + s;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> k = <span class="number">0</span>; k &lt;= K; ++k) f[<span class="number">0</span>][k] = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; ++i) &#123;</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> k = <span class="number">0</span>; k &lt;= K; ++k) &#123;</span><br><span class="line">                <span class="type">int</span> &amp;res = f[i][k];</span><br><span class="line">                <span class="keyword">if</span>(k) res = <span class="built_in">min</span>(res, f[i - <span class="number">1</span>][k - <span class="number">1</span>]);</span><br><span class="line">                <span class="type">int</span> same = <span class="number">0</span>, diff = <span class="number">0</span>;</span><br><span class="line">                <span class="keyword">for</span>(<span class="type">int</span> idx = i; idx &gt;= <span class="number">1</span>; --idx) &#123;</span><br><span class="line">                    <span class="keyword">if</span>(s[i] == s[idx]) &#123;</span><br><span class="line">                        ++same;</span><br><span class="line">                        res = <span class="built_in">min</span>(res, <span class="built_in">cal</span>(same) + f[idx - <span class="number">1</span>][k - diff]);</span><br><span class="line">                    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                        ++diff;</span><br><span class="line">                        <span class="keyword">if</span>(diff &gt; k) <span class="keyword">break</span>;</span><br><span class="line">                        res = <span class="built_in">min</span>(res, <span class="built_in">cal</span>(same) + f[idx - <span class="number">1</span>][k - diff]);</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> f[n][K];</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">cal</span><span class="params">(<span class="type">int</span> count)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(count == <span class="number">1</span>) <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">        string s = <span class="built_in">to_string</span>(count);</span><br><span class="line">        <span class="keyword">return</span> s.<span class="built_in">size</span>() + <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>





<h2 id="二分"><a href="#二分" class="headerlink" title="二分"></a>二分</h2><h3 id="两个有序数组找topk"><a href="#两个有序数组找topk" class="headerlink" title="两个有序数组找topk"></a>两个有序数组找topk</h3><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * find median in two sorted array</span></span><br><span class="line"><span class="comment">     * @param arr1 int整型vector the array1</span></span><br><span class="line"><span class="comment">     * @param arr2 int整型vector the array2</span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">getK</span><span class="params">(<span class="type">int</span> k, vector&lt;<span class="type">int</span>&gt;&amp; a1, vector&lt;<span class="type">int</span>&gt;&amp; a2)</span> </span>&#123;</span><br><span class="line">        <span class="type">int</span> idx1 = <span class="number">0</span>, idx2 = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">while</span>(k) &#123;</span><br><span class="line">            <span class="keyword">if</span>(idx1 &gt;= a1.<span class="built_in">size</span>()) &#123;</span><br><span class="line">                <span class="keyword">return</span> a2[idx2 + k - <span class="number">1</span>];</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>(idx2 &gt;= a2.<span class="built_in">size</span>()) &#123;</span><br><span class="line">                <span class="keyword">return</span> a1[idx1 + k - <span class="number">1</span>];</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>(k == <span class="number">1</span>) &#123;</span><br><span class="line">                <span class="keyword">return</span> (<span class="built_in">min</span>(a1[idx1], a2[idx2]));</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">// k &gt;= 2</span></span><br><span class="line">            <span class="type">int</span> kk = k/<span class="number">2</span>;</span><br><span class="line">            <span class="type">int</span> del = <span class="number">0</span>;</span><br><span class="line">            <span class="type">int</span> newIdx1 = <span class="built_in">min</span>((<span class="type">int</span>)a1.<span class="built_in">size</span>(), idx1 + kk) - <span class="number">1</span>; <span class="comment">// 最后一个被del的元素的脚标</span></span><br><span class="line">            <span class="type">int</span> newIdx2 = <span class="built_in">min</span>((<span class="type">int</span>)a2.<span class="built_in">size</span>(), idx2 + kk) - <span class="number">1</span>;</span><br><span class="line">            <span class="keyword">if</span>(a1[newIdx1] &lt; a2[newIdx2]) &#123;</span><br><span class="line">                del = newIdx1 - idx1 + <span class="number">1</span>;</span><br><span class="line">                idx1 = newIdx1 + <span class="number">1</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                del = newIdx2 - idx2 + <span class="number">1</span>;</span><br><span class="line">                idx2 = newIdx2 + <span class="number">1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            k -= del;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">findMedianinTwoSortedAray</span><span class="params">(vector&lt;<span class="type">int</span>&gt;&amp; arr1, vector&lt;<span class="type">int</span>&gt;&amp; arr2)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">getK</span>(arr1.<span class="built_in">size</span>(), arr1, arr2);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<h3 id="NC164-最长上升子序列-二"><a href="#NC164-最长上升子序列-二" class="headerlink" title="NC164 最长上升子序列(二)"></a><strong>NC164</strong> <strong>最长上升子序列(二)</strong></h3><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * 该数组最长严格上升子序列的长度</span></span><br><span class="line"><span class="comment">     * @param a int整型vector 给定的数组</span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">LIS</span><span class="params">(vector&lt;<span class="type">int</span>&gt;&amp; a)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        vector&lt;<span class="type">int</span>&gt; res;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> x: a) &#123;</span><br><span class="line">            <span class="keyword">if</span>(res.<span class="built_in">empty</span>() || x &gt; res.<span class="built_in">back</span>()) &#123;</span><br><span class="line">                res.<span class="built_in">push_back</span>(x);</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="type">int</span> idx = <span class="built_in">upper_bound</span>(res.<span class="built_in">begin</span>(), res.<span class="built_in">end</span>(), x) - res.<span class="built_in">begin</span>();</span><br><span class="line">                res[idx] = x;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> res.<span class="built_in">size</span>();</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>





<h2 id="回溯"><a href="#回溯" class="headerlink" title="回溯"></a>回溯</h2><h3 id="数独"><a href="#数独" class="headerlink" title="数独"></a>数独</h3><p>NC47 数独</p>
<p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/5e6c424b82224b85b64f28fd85761280?tpId=117&tqId=37743&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=100&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/5e6c424b82224b85b64f28fd85761280?tpId=117&amp;tqId=37743&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D100%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line">    <span class="type">const</span> <span class="type">static</span> <span class="type">int</span> N = <span class="number">9</span>;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="type">int</span> choice[N][N] = &#123;<span class="number">0</span>&#125;;</span><br><span class="line">    vector&lt;vector&lt;<span class="type">char</span>&gt; &gt; g;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">void</span> <span class="title">solveSudoku</span><span class="params">(vector&lt;vector&lt;<span class="type">char</span>&gt; &gt; &amp;board)</span> </span>&#123;</span><br><span class="line">        g = board;</span><br><span class="line">        <span class="keyword">if</span>(<span class="built_in">ok</span>()) <span class="keyword">return</span>;</span><br><span class="line">        pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt; p = <span class="built_in">pickBestPoint</span>();</span><br><span class="line">        <span class="built_in">dfs</span>(p.first, p.second);</span><br><span class="line">        board = g;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">bool</span> <span class="title">dfs</span><span class="params">(<span class="type">int</span> x, <span class="type">int</span> y)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(x == <span class="number">-1</span>) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        vector&lt;<span class="type">char</span>&gt; cs = <span class="built_in">calChoice</span>(x, y);</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">char</span> c: cs) &#123;</span><br><span class="line">            g[x][y] = c;</span><br><span class="line">            <span class="keyword">if</span>(<span class="built_in">ok</span>()) <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">            pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt; p = <span class="built_in">pickBestPoint</span>();</span><br><span class="line">            <span class="keyword">if</span>(<span class="built_in">dfs</span>(p.first, p.second)) &#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        g[x][y] = <span class="string">&#x27;.&#x27;</span>; <span class="comment">// key</span></span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">bool</span> <span class="title">ok</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; N; ++i) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; N; ++j) &#123;</span><br><span class="line">                <span class="keyword">if</span>(g[i][j] == <span class="string">&#x27;.&#x27;</span>) &#123;</span><br><span class="line">                    <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function">pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt; <span class="title">pickBestPoint</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="built_in">calChoice</span>();</span><br><span class="line">        <span class="type">int</span> m = <span class="number">10</span>;</span><br><span class="line">        pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt; p&#123;<span class="number">-1</span>, <span class="number">-1</span>&#125;;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; N; ++i) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; N; ++j) &#123;</span><br><span class="line">                <span class="keyword">if</span>(g[i][j] == <span class="string">&#x27;.&#x27;</span>) &#123;</span><br><span class="line">                    <span class="keyword">if</span> (choice[i][j] &lt; m) &#123;</span><br><span class="line">                        m = choice[i][j];</span><br><span class="line">                        p = <span class="built_in">make_pair</span>(i, j);</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> p;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">void</span> <span class="title">calChoice</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; N; ++i) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; N; ++j) &#123;</span><br><span class="line">                choice[i][j] = <span class="built_in">calChoice</span>(i, j).<span class="built_in">size</span>();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function">vector&lt;<span class="type">char</span>&gt; <span class="title">calChoice</span><span class="params">(<span class="type">int</span> x, <span class="type">int</span> y)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (g[x][y] != <span class="string">&#x27;.&#x27;</span>) <span class="keyword">return</span> &#123;&#125;;</span><br><span class="line">        set&lt;<span class="type">char</span>&gt; st;</span><br><span class="line">        <span class="comment">// row</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; N; ++j) &#123;</span><br><span class="line">            st.<span class="built_in">insert</span>(g[x][j]);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// col</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; N; ++i) &#123;</span><br><span class="line">            st.<span class="built_in">insert</span>(g[i][y]);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// box</span></span><br><span class="line">        x = (x / <span class="number">3</span>) * <span class="number">3</span>;</span><br><span class="line">        y = (y / <span class="number">3</span>) * <span class="number">3</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; <span class="number">3</span>; ++i) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; <span class="number">3</span>; ++j) &#123;</span><br><span class="line">                st.<span class="built_in">insert</span>(g[x + i][y + j]);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        vector&lt;<span class="type">char</span>&gt; ans;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">char</span> c = <span class="string">&#x27;1&#x27;</span>; c &lt;= <span class="string">&#x27;9&#x27;</span>; ++c) &#123;</span><br><span class="line">            <span class="keyword">if</span> (st.<span class="built_in">find</span>(c) == st.<span class="built_in">end</span>()) &#123;</span><br><span class="line">                ans.<span class="built_in">push_back</span>(c);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> ans;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>





<p>更简洁的写法：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="type">void</span> <span class="title">solveSudoku</span><span class="params">(vector&lt;vector&lt;<span class="type">char</span>&gt; &gt; &amp;board)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (!board.<span class="built_in">size</span>() || !board[<span class="number">0</span>].<span class="built_in">size</span>()) </span><br><span class="line">            <span class="keyword">return</span>; </span><br><span class="line">        <span class="built_in">helper</span>(board); </span><br><span class="line">        <span class="keyword">return</span>; </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="type">bool</span> <span class="title">judgeValid</span><span class="params">(vector&lt;vector&lt;<span class="type">char</span>&gt; &gt; &amp;board, <span class="type">int</span> target, <span class="type">int</span> row, <span class="type">int</span> col)</span> </span>&#123;</span><br><span class="line">        <span class="type">char</span> ch = target + <span class="string">&#x27;0&#x27;</span>; </span><br><span class="line">        <span class="comment">// 判断每一行是否有效</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; board[<span class="number">0</span>].<span class="built_in">size</span>(); i ++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (board[row][i] == ch) </span><br><span class="line">                <span class="keyword">return</span> <span class="literal">false</span>; </span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 判断每一列是否有效</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; board.<span class="built_in">size</span>(); i ++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (board[i][col] == ch) </span><br><span class="line">                <span class="keyword">return</span> <span class="literal">false</span>; </span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 判断每一个方块是否有效</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = (row / <span class="number">3</span>) * <span class="number">3</span>; i &lt; (row / <span class="number">3</span>) * <span class="number">3</span> + <span class="number">3</span>; i ++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> j = (col / <span class="number">3</span>) * <span class="number">3</span>; j &lt; (col / <span class="number">3</span>) * <span class="number">3</span> + <span class="number">3</span>; j ++) &#123;</span><br><span class="line">                <span class="keyword">if</span> (board[i][j] == ch) </span><br><span class="line">                    <span class="keyword">return</span> <span class="literal">false</span>; </span><br><span class="line">            &#125; </span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span>; </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="type">bool</span> <span class="title">helper</span><span class="params">(vector&lt;vector&lt;<span class="type">char</span>&gt; &gt; &amp;board)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; board.<span class="built_in">size</span>(); i ++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; board[<span class="number">0</span>].<span class="built_in">size</span>(); j ++) &#123;</span><br><span class="line">                <span class="comment">// 如果已经被填写，则跳过</span></span><br><span class="line">                <span class="keyword">if</span> (board[i][j] != <span class="string">&#x27;.&#x27;</span>) </span><br><span class="line">                    <span class="keyword">continue</span>; </span><br><span class="line">                <span class="comment">// 从1至9进行遍历</span></span><br><span class="line">                <span class="keyword">for</span> (<span class="type">int</span> k = <span class="number">1</span>; k &lt;= <span class="number">9</span>; k ++) &#123;</span><br><span class="line">                    <span class="keyword">if</span> (<span class="built_in">judgeValid</span>(board, k, i, j)) &#123; <span class="comment">// 如果是有效的</span></span><br><span class="line">                        board[i][j] = (k + <span class="string">&#x27;0&#x27;</span>); </span><br><span class="line">                        <span class="keyword">if</span> (<span class="built_in">helper</span>(board)) <span class="comment">// 继续求解，并找到一个解</span></span><br><span class="line">                            <span class="keyword">return</span> <span class="literal">true</span>; </span><br><span class="line">                        <span class="keyword">else</span></span><br><span class="line">                            board[i][j] = <span class="string">&#x27;.&#x27;</span>;  <span class="comment">// 没能找到答案，重置</span></span><br><span class="line">                    &#125; </span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">return</span> <span class="literal">false</span>; </span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span>; </span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<h3 id="NC182-单词拆分-二"><a href="#NC182-单词拆分-二" class="headerlink" title="NC182 单词拆分(二)"></a><strong>NC182</strong> <strong>单词拆分(二)</strong></h3><p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/bb40e0aae84a4491a35f93b322516cb5?tpId=117&tqId=39349&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=100&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/bb40e0aae84a4491a35f93b322516cb5?tpId=117&amp;tqId=39349&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D100%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * @param s string字符串</span></span><br><span class="line"><span class="comment">     * @param dic string字符串vector</span></span><br><span class="line"><span class="comment">     * @return string字符串vector</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    vector&lt;vector&lt;string&gt;&gt; ans;</span><br><span class="line">    vector&lt;string&gt; res;</span><br><span class="line">    unordered_set&lt;string&gt; dict;</span><br><span class="line"></span><br><span class="line">    <span class="function">vector&lt;string&gt; <span class="title">wordDiv</span><span class="params">(string word, vector&lt;string&gt; &amp;dic)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        <span class="keyword">for</span> (string &amp;s: dic) &#123;</span><br><span class="line">            dict.<span class="built_in">insert</span>(s);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">dfs</span>(<span class="number">0</span>, word);</span><br><span class="line">        vector&lt;string&gt; finalAns;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">auto</span> &amp;ss: ans) &#123;</span><br><span class="line">            string tmp;</span><br><span class="line">            <span class="keyword">for</span> (string &amp;s: ss) &#123;</span><br><span class="line">                tmp += s + <span class="string">&quot; &quot;</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            tmp.<span class="built_in">pop_back</span>();</span><br><span class="line">            finalAns.<span class="built_in">push_back</span>(tmp);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> finalAns;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">void</span> <span class="title">dfs</span><span class="params">(<span class="type">int</span> idx, <span class="type">const</span> string &amp;s)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (idx &gt;= s.<span class="built_in">length</span>()) &#123;</span><br><span class="line">            <span class="keyword">if</span> (idx == s.<span class="built_in">length</span>()) &#123;</span><br><span class="line">                ans.<span class="built_in">push_back</span>(res);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> cnt = <span class="number">1</span>; (idx + cnt) &lt;= s.<span class="built_in">size</span>(); ++cnt) &#123;</span><br><span class="line">            string w = s.<span class="built_in">substr</span>(idx, cnt);</span><br><span class="line">            <span class="keyword">if</span> (dict.<span class="built_in">find</span>(w) != dict.<span class="built_in">end</span>()) &#123;</span><br><span class="line">                res.<span class="built_in">push_back</span>(w);</span><br><span class="line">                <span class="built_in">dfs</span>(idx + cnt, s);</span><br><span class="line">                res.<span class="built_in">pop_back</span>();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>





<h2 id="栈"><a href="#栈" class="headerlink" title="栈"></a>栈</h2><h3 id="NC171-直方图内最大矩形"><a href="#NC171-直方图内最大矩形" class="headerlink" title="NC171 直方图内最大矩形"></a><strong>NC171</strong> <strong>直方图内最大矩形</strong></h3><p>单调栈</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * @param heights int整型vector</span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">typedef</span> pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt; P;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">largestRectangleArea</span><span class="params">(vector&lt;<span class="type">int</span>&gt; &amp;heights)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        <span class="type">int</span> ans = <span class="number">0</span>;</span><br><span class="line">        stack&lt;P&gt; st;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> h: heights) &#123;</span><br><span class="line">            <span class="keyword">if</span> (st.<span class="built_in">empty</span>() || h &gt;= st.<span class="built_in">top</span>().first) &#123;</span><br><span class="line">                st.<span class="built_in">push</span>(&#123;h, <span class="number">1</span>&#125;);</span><br><span class="line">                <span class="keyword">continue</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="type">int</span> sumWidth = <span class="number">0</span>;</span><br><span class="line">            <span class="keyword">while</span> (!st.<span class="built_in">empty</span>() &amp;&amp; h &lt; st.<span class="built_in">top</span>().first) &#123;</span><br><span class="line">                P p = st.<span class="built_in">top</span>();</span><br><span class="line">                ans = <span class="built_in">max</span>(ans, p.first * (p.second + sumWidth));</span><br><span class="line">                sumWidth += p.second;</span><br><span class="line">                st.<span class="built_in">pop</span>();</span><br><span class="line">            &#125;</span><br><span class="line">            st.<span class="built_in">push</span>(&#123;h, sumWidth + <span class="number">1</span>&#125;);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="type">int</span> sumWidth = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">while</span> (!st.<span class="built_in">empty</span>()) &#123;</span><br><span class="line">            P p = st.<span class="built_in">top</span>();</span><br><span class="line">            ans = <span class="built_in">max</span>(ans, p.first * (p.second + sumWidth));</span><br><span class="line">            sumWidth += p.second;</span><br><span class="line">            st.<span class="built_in">pop</span>();</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> ans;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>





<h3 id="NC237-最大矩形"><a href="#NC237-最大矩形" class="headerlink" title="NC237 最大矩形"></a><strong>NC237</strong> <strong>最大矩形</strong></h3><p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/5720efc1bdff4ca3a7dad37ca012cb60?tpId=117&tqId=39474&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=100&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/5720efc1bdff4ca3a7dad37ca012cb60?tpId=117&amp;tqId=39474&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D100%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<p>这个地方可以抽象、转化成上面的<strong>直方图内最大矩形</strong>，很需要想象力和转换能力。整体时间复杂度为O(m*n*n)</p>
<p>使用单调栈，可以优化到O(m*n)。不过这里使用另一种也不错的方式解决。</p>
<p><strong>枚举+前缀和</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * @param matrix int整型vector&lt;vector&lt;&gt;&gt;</span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">maximalRectangle</span><span class="params">(vector&lt;vector&lt;<span class="type">int</span>&gt; &gt; &amp;g)</span> </span>&#123;</span><br><span class="line">        <span class="type">int</span> m = g.<span class="built_in">size</span>();</span><br><span class="line">        <span class="type">int</span> n = g[<span class="number">0</span>].<span class="built_in">size</span>();</span><br><span class="line">        vector&lt;vector&lt;<span class="type">int</span>&gt;&gt; <span class="built_in">ps</span>(m, <span class="built_in">vector</span>&lt;<span class="type">int</span>&gt;(n));</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; m; ++i) &#123;</span><br><span class="line">            vector&lt;<span class="type">int</span>&gt; &amp;p = ps[i];</span><br><span class="line">            vector&lt;<span class="type">int</span>&gt; &amp;a = g[i];</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; n; ++j) &#123;</span><br><span class="line">                p[j] = j ? p[j - <span class="number">1</span>] + a[j] : a[j];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="type">int</span> ans = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> j1 = <span class="number">0</span>; j1 &lt; n; ++j1) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="type">int</span> j2 = j1; j2 &lt; n; ++j2) &#123;</span><br><span class="line">                <span class="type">int</span> now = <span class="number">0</span>;</span><br><span class="line">                <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; m; ++i) &#123;</span><br><span class="line">                    <span class="type">int</span> s = ps[i][j2] - (j1 ? ps[i][j1 - <span class="number">1</span>] : <span class="number">0</span>);</span><br><span class="line">                    <span class="type">bool</span> ok = s == j2 - j1 + <span class="number">1</span>;</span><br><span class="line">                    <span class="keyword">if</span> (ok) &#123;</span><br><span class="line">                        ++now;</span><br><span class="line">                        ans = <span class="built_in">max</span>(ans, now * (j2 - j1 + <span class="number">1</span>));</span><br><span class="line">                    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                        now = <span class="number">0</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">                ans = <span class="built_in">max</span>(ans, now * (j2 - j1 + <span class="number">1</span>));</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> ans;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<blockquote>
<p>题解</p>
<p><a target="_blank" rel="noopener" href="https://song-yang-ji.blog.csdn.net/article/details/107504273">https://song-yang-ji.blog.csdn.net/article/details/107504273</a></p>
</blockquote>
<h3 id="NC240-计算器-一"><a href="#NC240-计算器-一" class="headerlink" title="NC240 计算器(一)"></a><strong>NC240</strong> <strong>计算器(一)</strong></h3><p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/9b1fca7407954ba5a6f217e7c3537fed?tpId=117&tqId=39585&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=100&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/9b1fca7407954ba5a6f217e7c3537fed?tpId=117&amp;tqId=39585&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D100%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * @param s string字符串</span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    stack&lt;<span class="type">int</span>&gt; nums;</span><br><span class="line">    stack&lt;<span class="type">char</span>&gt; opts;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">void</span> <span class="title">handle</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="type">int</span> b = nums.<span class="built_in">top</span>();</span><br><span class="line">        nums.<span class="built_in">pop</span>();</span><br><span class="line">        <span class="type">int</span> a = nums.<span class="built_in">top</span>();</span><br><span class="line">        nums.<span class="built_in">pop</span>();</span><br><span class="line">        <span class="type">char</span> c = opts.<span class="built_in">top</span>();</span><br><span class="line">        opts.<span class="built_in">pop</span>();</span><br><span class="line">        <span class="type">int</span> res;</span><br><span class="line">        <span class="keyword">switch</span> (c) &#123;</span><br><span class="line">            <span class="keyword">case</span> <span class="string">&#x27;+&#x27;</span>:</span><br><span class="line">                res = a + b;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            <span class="keyword">case</span> <span class="string">&#x27;-&#x27;</span>:</span><br><span class="line">                res = a - b;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        nums.<span class="built_in">push</span>(res);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">calculate</span><span class="params">(string s)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (!<span class="built_in">isNumber</span>(s[<span class="number">0</span>])) &#123;</span><br><span class="line">            s = <span class="string">&quot;0&quot;</span> + s;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// write code here</span></span><br><span class="line">        <span class="type">int</span> i;</span><br><span class="line">        <span class="type">int</span> n = s.<span class="built_in">size</span>();</span><br><span class="line">        <span class="keyword">for</span> (i = <span class="number">0</span>; i &lt; s.<span class="built_in">length</span>();) &#123;</span><br><span class="line">            <span class="keyword">if</span> (<span class="built_in">isNumber</span>(s[i])) &#123;</span><br><span class="line">                <span class="type">int</span> num = <span class="number">0</span>;</span><br><span class="line">                <span class="keyword">while</span> (i &lt; n &amp;&amp; <span class="built_in">isNumber</span>(s[i])) &#123;</span><br><span class="line">                    num = num * <span class="number">10</span> + (s[i++] - <span class="string">&#x27;0&#x27;</span>);</span><br><span class="line">                &#125;</span><br><span class="line">                nums.<span class="built_in">push</span>(num);</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="keyword">if</span> (s[i] == <span class="string">&#x27;(&#x27;</span>) &#123;</span><br><span class="line">                    opts.<span class="built_in">push</span>(s[i]);</span><br><span class="line">                &#125; <span class="keyword">else</span> <span class="keyword">if</span> (s[i] == <span class="string">&#x27;)&#x27;</span>) &#123;</span><br><span class="line">                    <span class="type">char</span> opt;</span><br><span class="line">                    <span class="keyword">while</span> ((opt = opts.<span class="built_in">top</span>()) &amp;&amp; opt != <span class="string">&#x27;(&#x27;</span>) &#123;</span><br><span class="line">                        <span class="built_in">handle</span>();</span><br><span class="line">                    &#125;</span><br><span class="line">                    opts.<span class="built_in">pop</span>();</span><br><span class="line">                &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                    <span class="keyword">while</span> (!(opts.<span class="built_in">empty</span>() || opts.<span class="built_in">top</span>() == <span class="string">&#x27;(&#x27;</span>)) &#123;</span><br><span class="line">                        <span class="built_in">handle</span>();</span><br><span class="line">                    &#125;</span><br><span class="line">                    opts.<span class="built_in">push</span>(s[i]);</span><br><span class="line">                &#125;</span><br><span class="line">                ++i;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">while</span> (!opts.<span class="built_in">empty</span>()) &#123;</span><br><span class="line">            <span class="built_in">handle</span>();</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> nums.<span class="built_in">top</span>();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="type">bool</span> <span class="title">isNumber</span><span class="params">(<span class="type">char</span> c)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="string">&#x27;0&#x27;</span> &lt;= c &amp;&amp; c &lt;= <span class="string">&#x27;9&#x27;</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>





<h2 id="其他"><a href="#其他" class="headerlink" title="其他"></a>其他</h2><p>NC130 分糖果问题</p>
<p><a target="_blank" rel="noopener" href="https://www.nowcoder.com/practice/76039109dd0b47e994c08d8319faa352?tpId=117&tqId=37806&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?difficulty=4&judgeStatus=3&page=1&pageSize=100&search=&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=117&difficulty=4&judgeStatus=3&tags=&title=">https://www.nowcoder.com/practice/76039109dd0b47e994c08d8319faa352?tpId=117&amp;tqId=37806&amp;rp=1&amp;ru=/exam/oj&amp;qru=/exam/oj&amp;sourceUrl=%2Fexam%2Foj%3Fdifficulty%3D4%26judgeStatus%3D3%26page%3D1%26pageSize%3D100%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&amp;difficulty=4&amp;judgeStatus=3&amp;tags=&amp;title=</a></p>
<p>solution: 对于某个位置，计算从前&#x2F;后遍历，递增的位次，即连续递增的次数。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">define</span> inf 0x3f3f3f3f</span></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * pick candy</span></span><br><span class="line"><span class="comment">     * @param arr int整型vector the array</span></span><br><span class="line"><span class="comment">     * @return int整型</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">candy</span><span class="params">(vector&lt;<span class="type">int</span>&gt; &amp;a)</span> </span>&#123;</span><br><span class="line">        <span class="type">int</span> n = a.<span class="built_in">size</span>();</span><br><span class="line">        a.<span class="built_in">insert</span>(a.<span class="built_in">begin</span>(), inf);</span><br><span class="line">        a.<span class="built_in">push_back</span>(inf);</span><br><span class="line">        <span class="function">vector&lt;<span class="type">int</span>&gt; <span class="title">f1</span><span class="params">(n + <span class="number">10</span>)</span></span>;</span><br><span class="line">        <span class="function">vector&lt;<span class="type">int</span>&gt; <span class="title">f2</span><span class="params">(n + <span class="number">10</span>)</span></span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; ++i) &#123;</span><br><span class="line">            <span class="keyword">if</span>(a[i] &gt; a[i - <span class="number">1</span>]) &#123;</span><br><span class="line">                f1[i] = f1[i - <span class="number">1</span>] + <span class="number">1</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                f1[i] = <span class="number">0</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = n; i &gt;= <span class="number">1</span>; --i) &#123;</span><br><span class="line">            <span class="keyword">if</span>(a[i] &gt; a[i + <span class="number">1</span>]) &#123;</span><br><span class="line">                f2[i] = f2[i + <span class="number">1</span>] + <span class="number">1</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                f2[i] = <span class="number">0</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="type">int</span> ans = n;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</span><br><span class="line">            ans += <span class="built_in">max</span>(f1[i], f2[i]);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> ans;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>






      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="http://example.com/2022/06/27/%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91%E3%80%81%E5%93%88%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="SongyangJi">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="JsyBlog">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="undefined | JsyBlog">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2022/06/27/%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91%E3%80%81%E5%93%88%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81/" class="post-title-link" itemprop="url">哈夫曼树、哈夫曼编码</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2022-06-27 23:19:11" itemprop="dateCreated datePublished" datetime="2022-06-27T23:19:11+08:00">2022-06-27</time>
    </span>

  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          
      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="http://example.com/2022/06/20/Go%E8%AF%AD%E8%A8%80%E8%B0%83%E7%94%A8Shell%E4%B8%8E%E5%8F%AF%E6%89%A7%E8%A1%8C%E6%96%87%E4%BB%B6/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="SongyangJi">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="JsyBlog">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="undefined | JsyBlog">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2022/06/20/Go%E8%AF%AD%E8%A8%80%E8%B0%83%E7%94%A8Shell%E4%B8%8E%E5%8F%AF%E6%89%A7%E8%A1%8C%E6%96%87%E4%BB%B6/" class="post-title-link" itemprop="url">Go语言调用Shell与可执行文件</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2022-06-20 13:51:38" itemprop="dateCreated datePublished" datetime="2022-06-20T13:51:38+08:00">2022-06-20</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar-check"></i>
      </span>
      <span class="post-meta-item-text">更新于</span>
      <time title="修改时间：2022-09-02 22:44:06" itemprop="dateModified" datetime="2022-09-02T22:44:06+08:00">2022-09-02</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/Go/" itemprop="url" rel="index"><span itemprop="name">Go</span></a>
        </span>
    </span>

  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <h1 id="库函数"><a href="#库函数" class="headerlink" title="库函数"></a>库函数</h1><p>os&#x2F;exec包可用于调用外部命令，可以使用管道连接输入输出，并支持阻塞与非阻塞方式执行命令。<br>os&#x2F;exec包中关键的类型为Cmd，以下介绍的所有方法皆服务于该类型：</p>
<ul>
<li><p><code>func Command(name string, arg ...string) *Cmd</code><br> 方法返回一个*Cmd， 用于执行name指定的程序(携带arg参数)</p>
</li>
<li><p><code>func (c *Cmd) Run() error</code><br> 执行Cmd中包含的命令，阻塞直到命令执行完成</p>
</li>
<li><p><code>func (c *Cmd) Start() error</code><br> 执行Cmd中包含的命令，该方法立即返回，并不等待命令执行完成</p>
</li>
<li><p><code>func (c *Cmd) Wait() error</code><br> 该方法会阻塞直到Cmd中的命令执行完成，但该命令必须是被Start方法开始执行的</p>
</li>
<li><p><code>func (c *Cmd) Output() ([]byte, error)</code><br> 执行Cmd中包含的命令，并返回标准输出的切片</p>
</li>
<li><p><code>func (c *Cmd) CombinedOutput() ([]byte, error)</code><br> 执行Cmd中包含的命令，并返回标准输出与标准错误合并后的切片</p>
</li>
<li><p><code>func (c *Cmd) StdinPipe() (io.WriteCloser, error)</code><br> 返回一个管道，该管道会在Cmd中的命令被启动后连接到其标准输入</p>
</li>
<li><p><code>func (c *Cmd) StdoutPipe() (io.ReadCloser, error)</code><br> 返回一个管道，该管道会在Cmd中的命令被启动后连接到其标准输出</p>
</li>
<li><p><code>func (c *Cmd) StderrPipe() (io.ReadCloser, error)</code><br> 返回一个管道，该管道会在Cmd中的命令被启动后连接到其标准错误</p>
</li>
</ul>
<h1 id="普通调用示例"><a href="#普通调用示例" class="headerlink" title="普通调用示例"></a>普通调用示例</h1><h2 id="调用Shell命令或可执行文件"><a href="#调用Shell命令或可执行文件" class="headerlink" title="调用Shell命令或可执行文件"></a>调用Shell命令或可执行文件</h2><p>演示在当前目录创建一个空文件</p>
<figure class="highlight go"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> main</span><br><span class="line"></span><br><span class="line"><span class="keyword">import</span> (</span><br><span class="line">    <span class="string">&quot;fmt&quot;</span></span><br><span class="line">    <span class="string">&quot;os/exec&quot;</span></span><br><span class="line">)</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    cmd := exec.Command(<span class="string">&quot;touch&quot;</span>, <span class="string">&quot;test_file&quot;</span>)</span><br><span class="line"></span><br><span class="line">    err := cmd.Run()</span><br><span class="line">    <span class="keyword">if</span> err != <span class="literal">nil</span> &#123;</span><br><span class="line">        fmt.Println(<span class="string">&quot;Execute Command failed:&quot;</span> + err.Error())</span><br><span class="line">        <span class="keyword">return</span></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    fmt.Println(<span class="string">&quot;Execute Command finished.&quot;</span>)</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>一般不建议使用这种默认方式调用Shell脚本：<br><code>cmd := exec.Command(&quot;my_shell.sh&quot;)</code><br>因为这种方式实际的执行结果和命令行执行#sh my_shell.sh一样，如果你的Shell脚本不满足sh的规范，就会调用失败。</p>
<h2 id="调用Shell脚本"><a href="#调用Shell脚本" class="headerlink" title="调用Shell脚本"></a>调用Shell脚本</h2><p>设置bash来调用指定Shell脚本，dir_size.sh为我们测试用的Shell脚本。调用完成后打印Shell脚本的标准输出到控制台。</p>
<figure class="highlight go"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> main</span><br><span class="line"></span><br><span class="line"><span class="keyword">import</span> (</span><br><span class="line">    <span class="string">&quot;fmt&quot;</span></span><br><span class="line">    <span class="string">&quot;os/exec&quot;</span></span><br><span class="line">)</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    command := <span class="string">`./dir_size.sh .`</span></span><br><span class="line">    cmd := exec.Command(<span class="string">&quot;/bin/bash&quot;</span>, <span class="string">&quot;-c&quot;</span>, command)</span><br><span class="line"></span><br><span class="line">    output, err := cmd.Output()</span><br><span class="line">    <span class="keyword">if</span> err != <span class="literal">nil</span> &#123;</span><br><span class="line">        fmt.Printf(<span class="string">&quot;Execute Shell:%s failed with error:%s&quot;</span>, command, err.Error())</span><br><span class="line">        <span class="keyword">return</span></span><br><span class="line">    &#125;</span><br><span class="line">    fmt.Printf(<span class="string">&quot;Execute Shell:%s finished with output:\n%s&quot;</span>, command, <span class="type">string</span>(output))</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h2 id="使用输入输出Pipe"><a href="#使用输入输出Pipe" class="headerlink" title="使用输入输出Pipe"></a>使用输入输出Pipe</h2><p>演示使用管道连接到grep命令的标准输入，过滤包含test的字符串，并使用管道连接标准输出，打印运行结果：</p>
<figure class="highlight go"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> main</span><br><span class="line"></span><br><span class="line"><span class="keyword">import</span> (</span><br><span class="line">    <span class="string">&quot;fmt&quot;</span></span><br><span class="line">    <span class="string">&quot;io/ioutil&quot;</span></span><br><span class="line">    <span class="string">&quot;os/exec&quot;</span></span><br><span class="line">)</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">func</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    cmd := exec.Command(<span class="string">&quot;/bin/bash&quot;</span>, <span class="string">&quot;-c&quot;</span>, <span class="string">&quot;grep test&quot;</span>)</span><br><span class="line"></span><br><span class="line">    stdin, _ := cmd.StdinPipe()</span><br><span class="line">    stdout, _ := cmd.StdoutPipe()</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> err := cmd.Start(); err != <span class="literal">nil</span>&#123;</span><br><span class="line">        fmt.Println(<span class="string">&quot;Execute failed when Start:&quot;</span> + err.Error())</span><br><span class="line">        <span class="keyword">return</span></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    stdin.Write([]<span class="type">byte</span>(<span class="string">&quot;go text for grep\n&quot;</span>))</span><br><span class="line">    stdin.Write([]<span class="type">byte</span>(<span class="string">&quot;go test text for grep\n&quot;</span>))</span><br><span class="line">    stdin.Close()</span><br><span class="line"></span><br><span class="line">    out_bytes, _ := ioutil.ReadAll(stdout)</span><br><span class="line">    stdout.Close()</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> err := cmd.Wait(); err != <span class="literal">nil</span> &#123;</span><br><span class="line">        fmt.Println(<span class="string">&quot;Execute failed when Wait:&quot;</span> + err.Error())</span><br><span class="line">        <span class="keyword">return</span></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    fmt.Println(<span class="string">&quot;Execute finished:&quot;</span> + <span class="type">string</span>(out_bytes))</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>程序输出结果：</p>
<figure class="highlight shell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">[root@localhost ~]# ./execCommand </span><br><span class="line">Execute finished:go test text for grep</span><br></pre></td></tr></table></figure>
      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="http://example.com/2022/06/11/Docker%E5%BA%95%E5%B1%82%E6%A0%B8%E5%BF%83%E6%8A%80%E6%9C%AF-Namespace/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="SongyangJi">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="JsyBlog">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="undefined | JsyBlog">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2022/06/11/Docker%E5%BA%95%E5%B1%82%E6%A0%B8%E5%BF%83%E6%8A%80%E6%9C%AF-Namespace/" class="post-title-link" itemprop="url">Docker底层核心技术-Namespace</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2022-06-11 15:50:01" itemprop="dateCreated datePublished" datetime="2022-06-11T15:50:01+08:00">2022-06-11</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar-check"></i>
      </span>
      <span class="post-meta-item-text">更新于</span>
      <time title="修改时间：2022-10-18 19:50:02" itemprop="dateModified" datetime="2022-10-18T19:50:02+08:00">2022-10-18</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/Docker/" itemprop="url" rel="index"><span itemprop="name">Docker</span></a>
        </span>
    </span>

  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <blockquote>
<p>我们知道， Docker 是使用 Linux 的 Namespace 技术实现各种资源隔离的。那么究竟什么是 Namespace，各种 Namespace 都有什么作用，为什么 Docker 需要 Namespace呢？</p>
</blockquote>
<h1 id="什么是-Namespace？"><a href="#什么是-Namespace？" class="headerlink" title="什么是 Namespace？"></a>什么是 Namespace？</h1><p><code>Linux Namespace</code> 是 Linux 提供的一种内核级别环境隔离的方法。用官方的话来说，Linux Namespace 将全局系统资源封装在一个抽象中，从而使 namespace 内的进程认为自己具有独立的资源实例。这项技术本来没有掀起多大的波澜，是容器技术的崛起让他重新引起了大家的注意。</p>
<p>Linux Namespace 有如下 6 个种类：</p>
<table>
<thead>
<tr>
<th><strong>分类</strong></th>
<th><strong>系统调用参数</strong></th>
<th><strong>相关内核版本</strong></th>
</tr>
</thead>
<tbody><tr>
<td>Mount namespaces</td>
<td>CLONE_NEWNS</td>
<td><a target="_blank" rel="noopener" href="https://link.segmentfault.com/?enc=+UZjUSHsFnVMyxdIRI1AGg==.gjeALggXOGhl4I/K6t/Pu631zlrDabPYtH1Thy9PM6sQrfTxhZC7kHt+ChNg3UwF">Linux 2.4.19</a></td>
</tr>
<tr>
<td>UTS namespaces</td>
<td>CLONE_NEWUTS</td>
<td><a target="_blank" rel="noopener" href="https://link.segmentfault.com/?enc=UMCIjnpsL9NzRflD2ekSlw==.JUrNrso34Pdfy7WehLf8IbcdnOLCax6hnFPVZTIfm44=">Linux 2.6.19</a></td>
</tr>
<tr>
<td>IPC namespaces</td>
<td>CLONE_NEWIPC</td>
<td><a target="_blank" rel="noopener" href="https://link.segmentfault.com/?enc=mVHsSGWBKT/8S8FsszpQNg==.eMt8rtHaduUCEFo0KkpSywYvUBa1M0c6L/1vPeVf7Fg=">Linux 2.6.19</a></td>
</tr>
<tr>
<td>PID namespaces</td>
<td>CLONE_NEWPID</td>
<td><a target="_blank" rel="noopener" href="https://link.segmentfault.com/?enc=jYUd3r2qkaHvuIuS45YcNA==.F+FbhTmnrxXQ9og+jZ6YeUvF4OCSW+lbZh3QRIBW2qE=">Linux 2.6.24</a></td>
</tr>
<tr>
<td>Network namespaces</td>
<td>CLONE_NEWNET</td>
<td><a target="_blank" rel="noopener" href="https://link.segmentfault.com/?enc=B8NyDjpAtiUsjd4TxzKOFw==.mlMGKdt/sGvRRyFOFDguy/Xwnvgxyz8qGKBfpboNVO4=">始于Linux 2.6.24 完成于 Linux 2.6.29</a></td>
</tr>
<tr>
<td>User namespaces</td>
<td>CLONE_NEWUSER</td>
<td><a target="_blank" rel="noopener" href="https://link.segmentfault.com/?enc=5AgrP7X98up/uyck268Z9w==.Iem7g4brwXF4ER+OhdjlTQLCWYQSqFcei5K3MT5e9pA=">始于 Linux 2.6.23 完成于 Linux 3.8</a></td>
</tr>
</tbody></table>
<p><strong>namespace 的 API 由三个系统调用和一系列 <code>/proc</code> 文件组成</strong>。</p>
<p>本文将会详细介绍这些系统调用和 <code>/proc</code> 文件。为了指定要操作的 namespace 类型，需要在系统调用的 flag 中通过常量 <code>CLONE_NEW*</code> 指定（包括 <code>CLONE_NEWIPC</code>，<code>CLONE_NEWNS</code>， <code>CLONE_NEWNET</code>，<code>CLONE_NEWPID</code>，<code>CLONE_NEWUSER</code> 和 &#96;CLONE_NEWUTS），可以指定多个常量，通过 **|**（位或）操作来实现。</p>
<p>简单描述一下三个系统调用的功能：</p>
<ul>
<li><strong>clone()</strong> : 实现线程的系统调用，用来创建一个新的进程，并可以通过设计上述系统调用参数达到隔离的目的。</li>
<li><strong>unshare()</strong> : 使某进程脱离某个 namespace。</li>
<li><strong>setns()</strong> : 把某进程加入到某个 namespace。</li>
</ul>
<p>具体的实现原理请往下看。</p>
<h1 id="各种-Namespace-的作用？"><a href="#各种-Namespace-的作用？" class="headerlink" title="各种 Namespace 的作用？"></a>各种 Namespace 的作用？</h1><h2 id="Mount-Namespace"><a href="#Mount-Namespace" class="headerlink" title="Mount Namespace"></a>Mount Namespace</h2><p>Mount Namespace 是 Linux 内核实现的第一个 Namespace，从内核的 2.4.19 版本开始加入。它可以用来隔离不同的进程或进程组看到的挂载点。通俗地说，就是可以实现在不同的进程中看到不同的挂载目录。使用 Mount Namespace 可以实现容器内只能看到自己的挂载信息，在容器内的挂载操作不会影响主机的挂载目录。</p>
<h2 id="PID-Namespace"><a href="#PID-Namespace" class="headerlink" title="PID Namespace"></a>PID Namespace</h2><p>PID Namespace 的作用是用来隔离进程。在不同的 PID Namespace 中，进程可以拥有相同的 PID 号，利用 PID Namespace 可以实现每个容器的主进程为 1 号进程，而容器内的进程在主机上却拥有不同的PID。例如一个进程在主机上 PID 为 122，使用 PID Namespace 可以实现该进程在容器内看到的 PID 为 1。</p>
<p>下面我们通过一个实例来演示下 PID Namespace的作用。首先我们使用以下命令创建一个 bash 进程，并且新建一个 PID Namespace：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">$ sudo unshare --pid --fork --mount-proc /bin/bash</span><br><span class="line"></span><br><span class="line">[root@centos7 centos]#</span><br></pre></td></tr></table></figure>

<p>执行完上述命令后，我们在主机上创建了一个新的 PID Namespace，并且当前命令行窗口加入了新创建的 PID Namespace。在当前的命令行窗口使用 ps aux 命令查看一下进程信息：</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">[root@centos7 centos]# ps aux</span><br><span class="line"></span><br><span class="line">USER       PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND</span><br><span class="line"></span><br><span class="line">root         1  0.0  0.0 115544  2004 pts/0    S    10:57   0:00 bash</span><br><span class="line"></span><br><span class="line">root        10  0.0  0.0 155444  1764 pts/0    R+   10:59   0:00 ps aux</span><br></pre></td></tr></table></figure>

<p>通过上述命令输出结果可以看到当前 Namespace 下 bash 为 1 号进程，而且我们也看不到主机上的其他进程信息。</p>
<h2 id="UTS-Namespace"><a href="#UTS-Namespace" class="headerlink" title="UTS Namespace"></a>UTS Namespace</h2><p>UTS Namespace 主要是用来隔离主机名的，它允许每个 UTS Namespace 拥有一个独立的主机名。例如我们的主机名称为 docker，使用 UTS Namespace 可以实现在容器内的主机名称为 lagoudocker 或者其他任意自定义主机名。</p>
<p>同样我们通过一个实例来验证下 UTS Namespace 的作用，首先我们使用 unshare 命令来创建一个 UTS Namespace：</p>
<figure class="highlight perl"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">$ sudo unshare --uts --<span class="keyword">fork</span> /bin/bash</span><br><span class="line"></span><br><span class="line">[root@centos7 centos]<span class="comment">#</span></span><br></pre></td></tr></table></figure>

<p>创建好 UTS Namespace 后，当前命令行窗口已经处于一个独立的 UTS Namespace 中，下面我们使用 hostname 命令（hostname 可以用来查看主机名称）设置一下主机名：</p>
<figure class="highlight perl"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">root@centos7 centos]<span class="comment"># hostname -b lagoudocker</span></span><br></pre></td></tr></table></figure>

<p>然后再查看一下主机名：</p>
<figure class="highlight csharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">[<span class="meta">root@centos7 centos</span>]<span class="meta"># hostname</span></span><br><span class="line"></span><br><span class="line">lagoudocker</span><br></pre></td></tr></table></figure>

<p>通过上面命令的输出，我们可以看到当前UTS Namespace 内的主机名已经被修改为 lagoudocker。然后我们新打开一个命令行窗口，使用相同的命令查看一下主机的 hostname：</p>
<figure class="highlight ruby"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">[centos<span class="variable">@centos7</span> ~]<span class="variable">$ </span>hostname</span><br><span class="line"></span><br><span class="line">centos7</span><br></pre></td></tr></table></figure>

<p>可以看到主机的名称仍然为 centos7，并没有被修改。由此，可以验证 UTS Namespace 可以用来隔离主机名。</p>
<h2 id="IPC-Namespace"><a href="#IPC-Namespace" class="headerlink" title="IPC Namespace"></a>IPC Namespace</h2><p>IPC Namespace 主要是用来隔离进程间通信的。例如 PID Namespace 和 IPC Namespace 一起使用可以实现同一 IPC Namespace 内的进程彼此可以通信，不同 IPC Namespace 的进程却不能通信。</p>
<p>同样我们通过一个实例来验证下IPC Namespace的作用，首先我们使用 unshare 命令来创建一个 IPC Namespace：</p>
<figure class="highlight perl"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">$ sudo unshare --ipc --<span class="keyword">fork</span> /bin/bash</span><br><span class="line"></span><br><span class="line">[root@centos7 centos]<span class="comment">#</span></span><br></pre></td></tr></table></figure>

<p>下面我们需要借助两个命令来实现对 IPC Namespace 的验证。</p>
<ul>
<li>ipcs -q 命令：用来查看系统间通信队列列表。</li>
<li>ipcmk -Q 命令：用来创建系统间通信队列。</li>
</ul>
<p>我们首先使用 ipcs -q 命令查看一下当前 IPC Namespace 下的系统通信队列列表：</p>
<figure class="highlight ruby"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">[centos<span class="variable">@centos7</span> ~]<span class="variable">$ </span>ipcs -q</span><br><span class="line"></span><br><span class="line">------ <span class="title class_">Message</span> <span class="title class_">Queues</span> --------</span><br><span class="line"></span><br><span class="line">key        msqid      owner      perms      used-bytes   messages</span><br></pre></td></tr></table></figure>

<p>由上可以看到当前无任何系统通信队列，然后我们使用 ipcmk -Q 命令创建一个系统通信队列：</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">[root@centos7 centos]<span class="comment"># ipcmk -Q</span></span><br><span class="line"></span><br><span class="line">Message queue <span class="built_in">id</span>: 0</span><br></pre></td></tr></table></figure>

<p>再次使用 ipcs -q 命令查看当前 IPC Namespace 下的系统通信队列列表：</p>
<figure class="highlight csharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">[<span class="meta">root@centos7 centos</span>]<span class="meta"># ipcs -q</span></span><br><span class="line"></span><br><span class="line">------ Message Queues --------</span><br><span class="line"></span><br><span class="line">key        msqid      owner      perms      used-bytes   messages</span><br><span class="line"></span><br><span class="line"><span class="number">0x73682a32</span> <span class="number">0</span>          root       <span class="number">644</span>        <span class="number">0</span>            <span class="number">0</span></span><br></pre></td></tr></table></figure>

<p>可以看到我们已经成功创建了一个系统通信队列。然后我们新打开一个命令行窗口，使用ipcs -q 命令查看一下主机的系统通信队列：</p>
<figure class="highlight ruby"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">[centos<span class="variable">@centos7</span> ~]<span class="variable">$ </span>ipcs -q</span><br><span class="line"></span><br><span class="line">------ <span class="title class_">Message</span> <span class="title class_">Queues</span> --------</span><br><span class="line"></span><br><span class="line">key        msqid      owner      perms      used-bytes   messages</span><br></pre></td></tr></table></figure>

<p>通过上面的实验，可以发现，在单独的 IPC Namespace 内创建的系统通信队列在主机上无法看到。即 IPC Namespace 实现了系统通信队列的隔离。</p>
<h2 id="User-Namespace"><a href="#User-Namespace" class="headerlink" title="User Namespace"></a>User Namespace</h2><p>User Namespace 主要是用来隔离用户和用户组的。一个比较典型的应用场景就是在主机上以非 root 用户运行的进程可以在一个单独的 User Namespace 中映射成 root 用户。使用 User Namespace 可以实现进程在容器内拥有 root 权限，而在主机上却只是普通用户。</p>
<p>User Namesapce 的创建是可以不使用 root 权限的。下面我们以普通用户的身份创建一个 User Namespace，命令如下：</p>
<figure class="highlight ruby"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">[centos<span class="variable">@centos7</span> ~]<span class="variable">$ </span>unshare --user -r /bin/bash</span><br><span class="line"></span><br><span class="line">[root<span class="variable">@centos7</span> ~]<span class="comment">#</span></span><br></pre></td></tr></table></figure>

<blockquote>
<p>CentOS7 默认允许创建的 User Namespace 为 0，如果执行上述命令失败（ unshare 命令返回的错误为 unshare: unshare failed: Invalid argument ），需要使用以下命令修改系统允许创建的 User Namespace 数量，命令为：echo 65535 &gt; &#x2F;proc&#x2F;sys&#x2F;user&#x2F;max_user_namespaces，然后再次尝试创建 User Namespace。</p>
</blockquote>
<p>然后执行 id 命令查看一下当前的用户信息：</p>
<figure class="highlight ini"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="section">[root@centos7 ~]</span><span class="comment"># id</span></span><br><span class="line"></span><br><span class="line"><span class="attr">uid</span>=<span class="number">0</span>(root) gid=<span class="number">0</span>(root) groups=<span class="number">0</span>(root),<span class="number">65534</span>(nfsnobody) context=unconfined_u:unconfined_r:unconfined_t:s0-s0:c0.c1023</span><br></pre></td></tr></table></figure>

<p>通过上面的输出可以看到我们在新的 User Namespace 内已经是 root 用户了。下面我们使用只有主机 root 用户才可以执行的 reboot 命令来验证一下，在当前命令行窗口执行 reboot 命令：</p>
<figure class="highlight csharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">[<span class="meta">root@centos7 ~</span>]<span class="meta"># reboot</span></span><br><span class="line"></span><br><span class="line">Failed to open /dev/initctl: Permission denied</span><br><span class="line"></span><br><span class="line">Failed to talk to <span class="keyword">init</span> daemon.</span><br></pre></td></tr></table></figure>

<p>可以看到，我们在新创建的 User Namespace 内虽然是 root 用户，但是并没有权限执行 reboot 命令。这说明在隔离的 User Namespace 中，并不能获取到主机的 root 权限，也就是说 User Namespace 实现了用户和用户组的隔离。</p>
<h2 id="Net-Namespace"><a href="#Net-Namespace" class="headerlink" title="Net Namespace"></a>Net Namespace</h2><p>Net Namespace 是用来隔离网络设备、IP 地址和端口等信息的。Net Namespace 可以让每个进程拥有自己独立的 IP 地址，端口和网卡信息。例如主机 IP 地址为 172.16.4.1 ，容器内可以设置独立的 IP 地址为 192.168.1.1。</p>
<p>同样用实例验证，我们首先使用 ip a 命令查看一下主机上的网络信息：</p>
<figure class="highlight sql"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line">$ ip a</span><br><span class="line"></span><br><span class="line"><span class="number">1</span>: lo: <span class="operator">&lt;</span>LOOPBACK,UP,LOWER_UP<span class="operator">&gt;</span> mtu <span class="number">65536</span> qdisc noqueue state <span class="literal">UNKNOWN</span> <span class="keyword">group</span> <span class="keyword">default</span> qlen <span class="number">1000</span></span><br><span class="line"></span><br><span class="line">    link<span class="operator">/</span>loopback <span class="number">00</span>:<span class="number">00</span>:<span class="number">00</span>:<span class="number">00</span>:<span class="number">00</span>:<span class="number">00</span> brd <span class="number">00</span>:<span class="number">00</span>:<span class="number">00</span>:<span class="number">00</span>:<span class="number">00</span>:<span class="number">00</span></span><br><span class="line"></span><br><span class="line">    inet <span class="number">127.0</span><span class="number">.0</span><span class="number">.1</span><span class="operator">/</span><span class="number">8</span> <span class="keyword">scope</span> host lo</span><br><span class="line"></span><br><span class="line">       valid_lft forever preferred_lft forever</span><br><span class="line"></span><br><span class="line">    inet6 ::<span class="number">1</span><span class="operator">/</span><span class="number">128</span> <span class="keyword">scope</span> host</span><br><span class="line"></span><br><span class="line">       valid_lft forever preferred_lft forever</span><br><span class="line"></span><br><span class="line"><span class="number">2</span>: eth0: <span class="operator">&lt;</span>BROADCAST,MULTICAST,UP,LOWER_UP<span class="operator">&gt;</span> mtu <span class="number">1500</span> qdisc pfifo_fast state UP <span class="keyword">group</span> <span class="keyword">default</span> qlen <span class="number">1000</span></span><br><span class="line"></span><br><span class="line">    link<span class="operator">/</span>ether <span class="number">02</span>:<span class="number">11</span>:b0:<span class="number">14</span>:<span class="number">01</span>:<span class="number">0</span>c brd ff:ff:ff:ff:ff:ff</span><br><span class="line"></span><br><span class="line">    inet <span class="number">172.20</span><span class="number">.1</span><span class="number">.11</span><span class="operator">/</span><span class="number">24</span> brd <span class="number">172.20</span><span class="number">.1</span><span class="number">.255</span> <span class="keyword">scope</span> <span class="keyword">global</span> <span class="keyword">dynamic</span> eth0</span><br><span class="line"></span><br><span class="line">       valid_lft <span class="number">86063337</span>sec preferred_lft <span class="number">86063337</span>sec</span><br><span class="line"></span><br><span class="line">    inet6 fe80::<span class="number">11</span>:b0ff:fe14:<span class="number">10</span>c<span class="operator">/</span><span class="number">64</span> <span class="keyword">scope</span> link</span><br><span class="line"></span><br><span class="line">       valid_lft forever preferred_lft forever</span><br><span class="line"></span><br><span class="line"><span class="number">3</span>: docker0: <span class="operator">&lt;</span><span class="keyword">NO</span><span class="operator">-</span>CARRIER,BROADCAST,MULTICAST,UP<span class="operator">&gt;</span> mtu <span class="number">1500</span> qdisc noqueue state DOWN <span class="keyword">group</span> <span class="keyword">default</span></span><br><span class="line"></span><br><span class="line">    link<span class="operator">/</span>ether <span class="number">02</span>:<span class="number">42</span>:<span class="number">82</span>:<span class="number">8</span>d:a0:df brd ff:ff:ff:ff:ff:ff</span><br><span class="line"></span><br><span class="line">    inet <span class="number">172.17</span><span class="number">.0</span><span class="number">.1</span><span class="operator">/</span><span class="number">16</span> <span class="keyword">scope</span> <span class="keyword">global</span> docker0</span><br><span class="line"></span><br><span class="line">       valid_lft forever preferred_lft forever</span><br><span class="line"></span><br><span class="line">    inet6 fe80::<span class="number">42</span>:<span class="number">82</span>ff:fe8d:a0df<span class="operator">/</span><span class="number">64</span> <span class="keyword">scope</span> link</span><br><span class="line"></span><br><span class="line">       valid_lft forever preferred_lft forever</span><br></pre></td></tr></table></figure>

<p>然后我们使用以下命令创建一个 Net Namespace：</p>
<figure class="highlight perl"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">$ sudo unshare --net --<span class="keyword">fork</span> /bin/bash</span><br><span class="line"></span><br><span class="line">[root@centos7 centos]<span class="comment">#</span></span><br></pre></td></tr></table></figure>

<p>同样的我们使用 ip a 命令查看一下网络信息：</p>
<figure class="highlight csharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">[<span class="meta">root@centos7 centos</span>]<span class="meta"># ip a</span></span><br><span class="line"></span><br><span class="line"><span class="number">1</span>: lo: &lt;LOOPBACK&gt; mtu <span class="number">65536</span> qdisc noop state DOWN <span class="keyword">group</span> <span class="literal">default</span> qlen <span class="number">1000</span></span><br><span class="line"></span><br><span class="line">    link/loopback <span class="number">00</span>:<span class="number">00</span>:<span class="number">00</span>:<span class="number">00</span>:<span class="number">00</span>:<span class="number">00</span> brd <span class="number">00</span>:<span class="number">00</span>:<span class="number">00</span>:<span class="number">00</span>:<span class="number">00</span>:<span class="number">00</span></span><br></pre></td></tr></table></figure>

<p>可以看到，宿主机上有 lo、eth0、docker0 等网络设备，而我们新建的 Net Namespace 内则与主机上的网络设备不同。</p>
<h1 id="为什么-Docker-需要-Namespace？"><a href="#为什么-Docker-需要-Namespace？" class="headerlink" title="为什么 Docker 需要 Namespace？"></a>为什么 Docker 需要 Namespace？</h1><p>Linux 内核从 2002 年 2.4.19 版本开始加入了 Mount Namespace，而直到内核 3.8 版本加入了 User Namespace 才为容器提供了足够的支持功能。</p>
<p>当 Docker 新建一个容器时， 它会创建这六种 Namespace，然后将容器中的进程加入这些 Namespace 之中，使得 Docker 容器中的进程只能看到当前 Namespace 中的系统资源。</p>
<p>正是由于 Docker 使用了 Linux 的这些 Namespace 技术，才实现了 Docker 容器的隔离，可以说没有 Namespace，就没有 Docker 容器。</p>

      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="http://example.com/2022/06/11/%E6%9F%A5%E7%9C%8Bdocker%E5%AE%B9%E5%99%A8%E5%9C%A8%E5%AE%BF%E4%B8%BB%E6%9C%BA%E4%B8%AD%E7%9A%84pid/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="SongyangJi">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="JsyBlog">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="undefined | JsyBlog">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2022/06/11/%E6%9F%A5%E7%9C%8Bdocker%E5%AE%B9%E5%99%A8%E5%9C%A8%E5%AE%BF%E4%B8%BB%E6%9C%BA%E4%B8%AD%E7%9A%84pid/" class="post-title-link" itemprop="url">查看docker容器在宿主机中的pid</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>
      

      <time title="创建时间：2022-06-11 01:31:03 / 修改时间：01:33:50" itemprop="dateCreated datePublished" datetime="2022-06-11T01:31:03+08:00">2022-06-11</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/Docker/" itemprop="url" rel="index"><span itemprop="name">Docker</span></a>
        </span>
    </span>

  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <h2 id="1、使用linux-系统命令-ps-进行查找"><a href="#1、使用linux-系统命令-ps-进行查找" class="headerlink" title="1、使用linux 系统命令 ps 进行查找"></a>1、使用linux 系统命令 ps 进行查找</h2><figure class="highlight shell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">[root@web01 ~]# docker ps</span><br><span class="line">CONTAINER ID        IMAGE                  COMMAND                  CREATED             STATUS              PORTS                   NAMES</span><br><span class="line">7a8f16c97ec9        feisky/nginx:cpu-fix   &quot;nginx -g &#x27;daemon ...&quot;   3 hours ago         Up 3 hours          0.0.0.0:10000-&gt;80/tcp   nginx</span><br><span class="line"></span><br><span class="line">[root@web01 ~]# ps aux | grep 7a8f16c97ec9</span><br><span class="line">root      2824  0.0  0.0 112720   984 pts/2    R+   14:42   0:00 grep --color=auto 7a8f16c97ec9</span><br><span class="line">root     23837  0.0  0.1 264796  2972 ?        Sl   11:21   0:00 /usr/bin/docker-containerd-shim-current 7a8f16c97ec9e9750f8ef31fc24da3151562995c0d9e5837d2bf42c2885f3a27 /var/run/docker/libcontainerd/7a8f16c97ec9e9750f8ef31fc24da3151562995c0d9e5837d2bf42c2885f3a27 /usr/libexec/docker/docker-runc-current</span><br></pre></td></tr></table></figure>

<p>先使用docker ps 查看容器id，再通过容器id在系统中查找该进程。</p>
<h2 id="2、通过docker-inspect-进行查找"><a href="#2、通过docker-inspect-进行查找" class="headerlink" title="2、通过docker inspect 进行查找"></a>2、通过docker inspect 进行查找</h2><figure class="highlight shell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">[root@web01 ~]# docker ps</span><br><span class="line">CONTAINER ID        IMAGE                  COMMAND                  CREATED             STATUS              PORTS                   NAMES</span><br><span class="line">7a8f16c97ec9        feisky/nginx:cpu-fix   &quot;nginx -g &#x27;daemon ...&quot;   3 hours ago         Up 3 hours          0.0.0.0:10000-&gt;80/tcp   nginx</span><br><span class="line">[root@web01 ~]# docker inspect -f &#x27;&#123;&#123;.State.Pid&#125;&#125;&#x27; 7a8f16c97ec9</span><br><span class="line">23852</span><br></pre></td></tr></table></figure>

<p>当然docker inspect 的作用远不止如此，它能看到很多容器的配置信息，这里使用 -f 过滤出了pid信息。</p>
<h2 id="3、使用docker-container-top-进行查看"><a href="#3、使用docker-container-top-进行查看" class="headerlink" title="3、使用docker container top 进行查看"></a>3、使用docker container top 进行查看</h2><figure class="highlight shell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">[root@web01 ~]# docker ps</span><br><span class="line">CONTAINER ID        IMAGE                  COMMAND                  CREATED             STATUS              PORTS                   NAMES</span><br><span class="line">7a8f16c97ec9        feisky/nginx:cpu-fix   &quot;nginx -g &#x27;daemon ...&quot;   3 hours ago         Up 3 hours          0.0.0.0:10000-&gt;80/tcp   nginx</span><br><span class="line"></span><br><span class="line">[root@web01 ~]# docker container top 7a8f16c97ec9</span><br><span class="line">UID                 PID                 PPID                C                   STIME               TTY                 TIME                CMD</span><br><span class="line">root                23852               23837               0                   11:21               pts/1               00:00:00            nginx: master process nginx -g daemon off;</span><br><span class="line">101                 23899               23852               0                   11:21               pts/1               00:00:00            nginx: worker process</span><br><span class="line">101                 23900               23852               0                   11:21               pts/1               00:00:00            nginx: worker process</span><br></pre></td></tr></table></figure>

<p>这里显示了很多个pid 需要特别说明一下，容器的pid 是23852 ，PPID 是它的父进程。下面的101、102都是它的子进程。</p>

      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




    


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
    <link itemprop="mainEntityOfPage" href="http://example.com/2022/06/10/Docker%E5%AE%B9%E5%99%A8%E9%99%90%E5%88%B6Memory/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="SongyangJi">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="JsyBlog">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="undefined | JsyBlog">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h2 class="post-title" itemprop="name headline">
          <a href="/2022/06/10/Docker%E5%AE%B9%E5%99%A8%E9%99%90%E5%88%B6Memory/" class="post-title-link" itemprop="url">Docker容器限制Memory</a>
        </h2>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2022-06-10 10:49:04" itemprop="dateCreated datePublished" datetime="2022-06-10T10:49:04+08:00">2022-06-10</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar-check"></i>
      </span>
      <span class="post-meta-item-text">更新于</span>
      <time title="修改时间：2023-04-08 16:04:56" itemprop="dateModified" datetime="2023-04-08T16:04:56+08:00">2023-04-08</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/Docker/" itemprop="url" rel="index"><span itemprop="name">Docker</span></a>
        </span>
    </span>

  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">
          <blockquote>
<p>默认情况下容器使用的资源是不受限制的。也就是可以使用主机内核调度器所允许的最大资源。但是在容器的使用过程中，经常需要对容器可以使用的主机资源进行限制，本文介绍如何限制容器可以使用的主机内存。</p>
</blockquote>
<h1 id="压测工具"><a href="#压测工具" class="headerlink" title="压测工具"></a>压测工具</h1><p>使用ubuntu的<code>stress</code> 作为压测工具，并制作镜像</p>
<figure class="highlight dockerfile"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">FROM</span> ubuntu:latest</span><br><span class="line"></span><br><span class="line"><span class="keyword">RUN</span><span class="language-bash"> apt-get update &amp;&amp; \</span></span><br><span class="line"><span class="language-bash">        apt-get install stress</span></span><br></pre></td></tr></table></figure>
<p>shell命令</p>
<figure class="highlight shell"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">docker build -t u-stress:latest .</span><br></pre></td></tr></table></figure>







<h1 id="为什么要限制容器对内存的使用？"><a href="#为什么要限制容器对内存的使用？" class="headerlink" title="为什么要限制容器对内存的使用？"></a>为什么要限制容器对内存的使用？</h1><p>限制容器不能过多的使用主机的内存是非常重要的。对于 linux 主机来说，一旦内核检测到没有足够的内存可以分配，就会扔出 OOME(Out Of Memmory Exception)，并开始杀死一些进程用于释放内存空间。糟糕的是任何进程都可能成为内核猎杀的对象，包括 docker daemon 和其它一些重要的程序。更危险的是如果某个支持系统运行的重要进程被干掉了，整个系统也就宕掉了！这里我们考虑一个比较常见的场景，大量的容器把主机的内存消耗殆尽，OOME 被触发后系统内核立即开始杀进程释放内存。如果内核杀死的第一个进程就是 docker daemon 会怎么样？结果是没有办法管理运行中的容器了，这是不能接受的！<br>针对这个问题，docker 尝试通过调整 docker daemon 的 OOM 优先级来进行缓解。内核在选择要杀死的进程时会对所有的进程打分，直接杀死得分最高的进程，接着是下一个。当 docker daemon 的 OOM 优先级被降低后(注意容器进程的 OOM 优先级并没有被调整)，docker daemon 进程的得分不仅会低于容器进程的得分，还会低于其它一些进程的得分。这样 docker daemon 进程就安全多了。</p>
<p>我们可以通过下面的脚本直观的看一下当前系统中所有进程的得分情况：</p>
<figure class="highlight shell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta prompt_">#</span><span class="language-bash">!/bin/bash</span></span><br><span class="line">number=$1</span><br><span class="line">for proc in $(find /proc -maxdepth 1 -regex &#x27;/proc/[0-9]+&#x27;); do</span><br><span class="line">    printf &quot;%2d %5d %s\n&quot; \</span><br><span class="line">        &quot;$(cat $proc/oom_score)&quot; \</span><br><span class="line">        &quot;$(basename $proc)&quot; \</span><br><span class="line">        &quot;$(cat $proc/cmdline | tr &#x27;\0&#x27; &#x27; &#x27; | head -c 50)&quot;</span><br><span class="line">done 2&gt;/dev/null | sort -nr | head -n &quot;$number&quot;</span><br></pre></td></tr></table></figure>



<p>此脚本输出得分最高的 40 个进程，并进行了排序：</p>
<p><img src="/2022/06/10/Docker%E5%AE%B9%E5%99%A8%E9%99%90%E5%88%B6Memory/Docker%E5%AE%B9%E5%99%A8%E9%99%90%E5%88%B6Memory-0.png"></p>
<p>第一列显示进程的得分，mysqld 排到的第一名。显示为 node server.js 的都是容器进程，排名普遍比较靠前。红框中的是 docker daemon 进程，非常的靠后，都排到了 sshd 的后面。</p>
<p>有了上面的机制后是否就可以高枕无忧了呢！不是的，docker 的官方文档中一直强调这只是一种缓解的方案，并且为我们提供了一些降低风险的建议：</p>
<ul>
<li>通过测试掌握应用对内存的需求</li>
<li>保证运行容器的主机有充足的内存</li>
<li>限制容器可以使用的内存</li>
<li>为主机配置 swap</li>
</ul>
<p>其实就是说：通过限制容器使用的内存上限，可以降低主机内存耗尽时带来的各种风险。</p>
<h1 id="限制Memory"><a href="#限制Memory" class="headerlink" title="限制Memory"></a>限制Memory</h1><p>&#x2F;Users&#x2F;jisongyang&#x2F;go&#x2F;pkg&#x2F;mod&#x2F;github.com&#x2F;docker&#x2F;<a href="mailto:&#x64;&#111;&#x63;&#107;&#x65;&#x72;&#x40;&#x76;&#50;&#48;&#x2e;&#49;&#48;&#46;&#49;&#x35;">&#x64;&#111;&#x63;&#107;&#x65;&#x72;&#x40;&#x76;&#50;&#48;&#x2e;&#49;&#48;&#46;&#49;&#x35;</a>+incompatible&#x2F;api&#x2F;types&#x2F;container&#x2F;host_config.go</p>
<h2 id="限制内存使用上限"><a href="#限制内存使用上限" class="headerlink" title="限制内存使用上限"></a>限制内存使用上限</h2><p>使用<code>-m(--memory=)</code>可以限制容器使用的最大内存。</p>
<figure class="highlight shell"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">docker run -it -m 300M --memory-swap -1 --name con1 u-stress /bin/bash</span><br></pre></td></tr></table></figure>



<p>下面的 stress 命令会创建一个进程并通过 malloc 函数分配内存：</p>
<figure class="highlight shell"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">stress --vm 1 --vm-bytes 500M</span><br></pre></td></tr></table></figure>

<p>通过 docker stats 命令查看实际情况：<br><img src="/2022/06/10/Docker%E5%AE%B9%E5%99%A8%E9%99%90%E5%88%B6Memory/Docker%E5%AE%B9%E5%99%A8%E9%99%90%E5%88%B6Memory-1.png"></p>
<p>上面的 docker run 命令中通过 -m 选项限制容器使用的内存上限为 300M。同时设置 memory-swap 值为 -1，它表示容器程序使用内存的受限，而可以使用的 swap 空间使用不受限制(宿主机有多少 swap 容器就可以使用多少)。<br>下面我们通过 top 命令来查看 stress 进程内存的实际情况：<br><img src="/2022/06/10/Docker%E5%AE%B9%E5%99%A8%E9%99%90%E5%88%B6Memory/Docker%E5%AE%B9%E5%99%A8%E9%99%90%E5%88%B6Memory-2.png"></p>
<p>上面的截图中先通过 pgrep 命令查询 stress 命令相关的进程，进程号比较大的那个是用来消耗内存的进程，我们就查看它的内存信息。VIRT 是进程虚拟内存的大小，所以它应该是 500M。RES 为实际分配的物理内存数量，我们看到这个值就在 300M 上下浮动。看样子我们已经成功的限制了容器能够使用的物理内存数量。</p>
<h2 id="限制可用的-swap-大小"><a href="#限制可用的-swap-大小" class="headerlink" title="限制可用的 swap 大小"></a>限制可用的 swap 大小</h2><p>强调一下 –memory-swap 是必须要与 –memory 一起使用的。</p>
<p>正常情况下， –memory-swap 的值包含容器可用内存和可用 swap。所以 –memory&#x3D;”300m” –memory-swap&#x3D;”1g” 的含义为：<br>容器可以使用 300M 的物理内存，并且可以使用 700M(1G -300M) 的 swap。–memory-swap 是容器可以使用的物理内存和可以使用的 swap 之和。</p>
<p>把 –memory-swap 设置为 0 和不设置是一样的，此时如果设置了 –memory，容器可以使用的 swap 大小为 –memory 值的两倍。（也就是说缺省情况下swap空间刚好为1倍的memory）</p>
<p><strong>如果 –memory-swap 的值和 –memory 相同，则容器不能使用 swap</strong>。下面的 demo 演示了在没有 swap 可用的情况下向系统申请大量内存的场景：</p>
<figure class="highlight shell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta prompt_">$ </span><span class="language-bash">docker run -it --<span class="built_in">rm</span> -m 300M --memory-swap=300M u-stress /bin/bash</span></span><br><span class="line"><span class="meta prompt_"># </span><span class="language-bash">stress --vm 1 --vm-bytes 500M</span></span><br></pre></td></tr></table></figure>

<p><img src="/2022/06/10/Docker%E5%AE%B9%E5%99%A8%E9%99%90%E5%88%B6Memory/Docker%E5%AE%B9%E5%99%A8%E9%99%90%E5%88%B6Memory-3.png"></p>
<p>demo 中容器的物理内存被限制在 300M，但是进程却希望申请到 500M 的物理内存。在没有 swap 可用的情况下，进程直接被 OOM kill 了。如果有足够的 swap，程序至少还可以正常的运行。</p>
<p>我们可以通过 –oom-kill-disable 选项强行阻止 OOM kill 的发生，但是最好不要。</p>
<h1 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h1><p>通过限制容器可用的物理内存，可以避免容器内服务异常导致大量消耗主机内存的情况(此时让容器重启是较好的策略)，因此可以降低主机内存被耗尽带来的风险。</p>
<p><a target="_blank" rel="noopener" href="https://sanhe-dev-exp-share.readthedocs.io/03-Docker/03-Restrict-CPU-Memory-and-GPU/README.html">https://sanhe-dev-exp-share.readthedocs.io/03-Docker/03-Restrict-CPU-Memory-and-GPU/README.html</a></p>

      
    </div>

    
    
    

    <footer class="post-footer">
        <div class="post-eof"></div>
      
    </footer>
  </article>
</div>




  <nav class="pagination">
    <a class="extend prev" rel="prev" title="上一页" aria-label="上一页" href="/page/8/"><i class="fa fa-angle-left"></i></a><a class="page-number" href="/">1</a><span class="space">&hellip;</span><a class="page-number" href="/page/8/">8</a><span class="page-number current">9</span><a class="page-number" href="/page/10/">10</a><span class="space">&hellip;</span><a class="page-number" href="/page/26/">26</a><a class="extend next" rel="next" title="下一页" aria-label="下一页" href="/page/10/"><i class="fa fa-angle-right"></i></a>
  </nav>

</div>
  </main>

  <footer class="footer">
    <div class="footer-inner">


<div class="copyright">
  &copy; 
  <span itemprop="copyrightYear">2023</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">SongyangJi</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/muse/" rel="noopener" target="_blank">NexT.Muse</a> 强力驱动
  </div>

    </div>
  </footer>

  
  <div class="toggle sidebar-toggle" role="button">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>
  <div class="sidebar-dimmer"></div>
  <div class="back-to-top" role="button" aria-label="返回顶部">
    <i class="fa fa-arrow-up fa-lg"></i>
    <span>0%</span>
  </div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


  
  <script src="https://cdnjs.cloudflare.com/ajax/libs/animejs/3.2.1/anime.min.js" integrity="sha256-XL2inqUJaslATFnHdJOi9GfQ60on8Wx1C2H8DYiN1xY=" crossorigin="anonymous"></script>
<script src="/js/comments.js"></script><script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/schemes/muse.js"></script><script src="/js/next-boot.js"></script>

  <script src="https://cdnjs.cloudflare.com/ajax/libs/hexo-generator-searchdb/1.4.1/search.js" integrity="sha256-1kfA5uHPf65M5cphT2dvymhkuyHPQp5A53EGZOnOLmc=" crossorigin="anonymous"></script>
<script src="/js/third-party/search/local-search.js"></script>





  





</body>
</html>
